Article•2 hours ago

Fibonacci numbers

The Fibonacci sequence is one of the most well-known sequences in mathematics and computer science. It is named after the Italian mathematician Leonardo of Pisa, also known as Fibonacci.

h ttp s : // e n . w iki p e d ia . or g / w iki / F ib o na cc i_n u mb er

The Fibonacci numbers $f_{n} = f (n)$ form a sequence where each number after the first two is equal to the sum of the two preceding ones.

They are defined by the following recurrence relation:

f (n) = ⎩ ⎨ ⎧ 0, if n = 0 1, if n = 1 f (n - 1) + f (n - 2), if n \geq 2

Thus, we have:

f_{0} = 0, f_{1} = 1, f_{n} = f_{n - 1} + f_{n - 2}

The Fibonacci sequence therefore begins as:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Each term is obtained by adding the two previous terms.

Example. Compute Fibonacci numbers using an array.

The following program fills an integer array $f ib$ such that $f ib [i] = f_{i}$ , where $f_{i}$ is the $i$ -th Fibonacci number. It then prints the value $f ib [n]$ for a given input $n$ .

#include <stdio.h>

int i, n, fib[47];

int main(void)
{
  scanf("%d",&n);

  fib[0] = 0; fib[1] = 1;
  for(i = 2; i <= n; i++)
    fib[i] = fib[i-1] + fib[i-2];

  printf("%d\n",fib[n]);
  return 0;
}

The largest Fibonacci number that can be stored in the int data type is:

f_{46} = 1836311903

The largest Fibonacci number that can be stored in the long long data type is:

f_{92} = 7540113804746346429

For computing Fibonacci numbers with index $n > 92$ , standard integer types are no longer sufficient due to overflow. In such cases, arbitrary-precision arithmetic must be used, such as the BigInteger type (or equivalent big number libraries in programming languages that do not support built-in large integers).

Example. Compute the $n$ -th Fibonacci number using a recursive function.

The following program implements a direct recursive definition of the Fibonacci sequence. The function $f ib (n)$ returns the $n$ -th Fibonacci number according to the recurrence relation.

#include <stdio.h>

int n;

int fib(int n)
{
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n-1) + fib(n - 2);
}

int main(void)
{
  scanf("%d",&n);
  printf("%d\n",fib(n));
  return 0;
}

Example. Compute the $n$ -th Fibonacci number using recursion with memoization.

The following program implements a recursive solution enhanced with memoization to avoid redundant computations. Previously computed values are stored in an array, so each Fibonacci number is calculated at most once.

#include <stdio.h>
#include <string.h>
 
int n, fib[46];
 
int f(int n)
{
  // base cases
  if (n == 0) return 0;
  if (n == 1) return 1;

  // if fib[n] has already been computed, return it 
  if (fib[n] != -1) return fib[n]; 

  // otherwise compute and store (memoize) the result
  return fib[n] = f(n-1) + f(n - 2);
}
 
int main(void)
{
  scanf("%d",&n);

  // initialize memoization array:
  // fib[i] = -1 indicates that the value has not been computed yet 
  memset(fib,-1,sizeof(fib));

  printf("%d\n",f(n));
  return 0;
}

This approach significantly improves efficiency compared to plain recursion. While the naive recursive solution has exponential complexity, memoization reduces the time complexity to $O (n)$ , since each state is evaluated only once.

Java code

import java.util.*;

public class Main
{
  static int fib[] = new int[46];    
  
  static int f(int n)
  {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (fib[n] != -1) return fib[n];
    return fib[n] = f(n-1) + f(n - 2);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    Arrays.fill(fib, -1);
    System.out.println(f(n));     
    con.close();
  }
}

Prove the following properties of Fibonacci numbers:

f_{0} + f_{1} + f_{2} + f_{3} + ... + f_{n} = f_{n + 2} - 1

► Base case $n = 0 : f_{0} = f_{2} - 1$ . This is true since $0 = 1 - 1$ .

Inductive step. Assume that:

f_{0} + f_{1} + f_{2} + f_{3} + ... + f_{n - 1} = f_{n + 1} - 1

Then:

f_{0} + f_{1} + f_{2} + f_{3} + ... + f_{n} = (f_{0} + f_{1} + f_{2} + f_{3} + ... + f_{n - 1}) + f_{n} = (f_{n + 1} - 1) + f_{n} = f_{n + 2} - 1

f_{1} + f_{3} + f_{5} + ... + f_{2 n - 1} = f_{2 n}

► Base case $n = 1 : f_{1} = f_{2}$ , which holds since $1 = 1$ .

Inductive step. Assume:

f_{1} + f_{3} + f_{5} + ... + f_{2 n - 1} = f_{2 n}

Then:

f_{1} + f_{3} + ... + f_{2 n + 1} = (f_{1} + f_{3} + ... + f_{2 n - 1}) + f_{2 n + 1} = f_{2 n} + f_{2 n + 1} = f_{2 n + 2}

f_{2} + f_{4} + f_{6} + ... + f_{2 n} = f_{2 n + 1} - 1

► Base case $n = 1 : f_{2} = f_{3} - 1$ . This is true since $1 = 2 - 1$ .

Inductive step. Assume:

f_{2} + f_{4} + f_{6} + ... + f_{2 n} = f_{2 n + 1} - 1

Then:

f_{2} + f_{4} + ... + f_{2 n + 2} = (f_{2} + f_{4} + ... + f_{2 n}) + f_{2 n + 2} = (f_{2 n + 1} - 1) + f_{2 n + 2} = f_{2 n + 3} - 1

f_{0}^{2} + f_{1}^{2} + f_{2}^{2} + ... + f_{n}^{2} = f_{n} \cdot f_{n + 1}

► Base case $n = 0 : f_{0}^{2} = f_{0} \cdot f_{1}$ . This is true since $0 = 0 \cdot 1$ .

Inductive step. Assume:

f_{0}^{2} + f_{1}^{2} + f_{2}^{2} + ... + f_{n - 1}^{2} = f_{n - 1} \cdot f_{n}

Then:

f_{0}^{2} + f_{1}^{2} + f_{2}^{2} + ... + f_{n}^{2} = (f_{0}^{2} + f_{1}^{2} + f_{2}^{2} + ... + f_{n - 1}^{2}) + f_{n}^{2} = (f_{n - 1} \cdot f_{n}) + f_{n}^{2} = f_{n} \cdot (f_{n - 1} + f_{n}) = f_{n} \cdot f_{n + 1}

Compute the Fibonacci numbers and store them in the $f ib$ array: $f ib [i] = f (i)$ .

#define MAX 46
int fib[MAX];

Fill the $f ib$ array according to the recursive formula.

fib[0] = 1; fib[1] = 1;
for (int i = 2; i < MAX; i++)
  fib[i] = fib[i-1] + fib[i-2];

Read the input value of $n$ . Print the answer.

scanf("%d",&n);
printf("%d\n",fib[n]);

Algorithm implementation — recursion

Declare the $f ib$ array to store Fibonacci numbers: $f ib [i] = f (i)$ .

#define MAX 46
int fib[MAX];

The recursive function f computes the $n$ -th Fibonacci number. The memoization technique is used.

int f(int n)
{
  if (n <= 1) return 1;
  if (fib[n] != -1) return fib[n];
  return fib[n] = f(n-1) + f(n - 2);
}

The main part of the program. Read the value of $n$ .

scanf("%d",&n);

Assign the value of $- 1$ to all elements of $f ib$ array.

memset(fib,-1,sizeof(fib));

Compute and print the value $f (n)$ .

printf("%d\n",f(n));

Algorithm implementation — iteration

Read the input number $n$ .

scanf("%d", &n);

Handle the base case.

if (n == 0 || n == 1) 
{
  printf("1\n");
  return 0;
}

Let us assign:

the $0$ -th Fibonacci number to the variable $a$ ;
the $1$ -st Fibonacci number to the variable $b$ ;

Initially, the variables $a$ and $b$ contain two consecutive Fibonacci numbers.

a = b = 1;
for (i = 2; i <= n; i++) 
{

The variables $a$ and $b$ contain two consecutive Fibonacci numbers.

a = f (i - 2), b = f (i - 1)

Compute the next Fibonacci number:

c = a + b = f (i - 2) + f (i - 1) = f (i)

  c = a + b;

Perform a shift, as a result of which $a = f (i - 1)$ and $b = f (i)$ .

  a = b;
  b = c;
}

Print the answer. The variable $b$ contains the value of $f (n)$ .

printf("%lld\n", b);

NO two one's in a row

Find the number of sequences of length $n$ , consisting only of zeros and ones, that do not have two one's in a row.

Let $f (n)$ be the number of sequences consisting of $0$ and $1$ of length $n$ that do not have two one's in a row.

If the first number in the sequence is $0$ , then starting from the second place we can build $f (n - 1)$ sequences.

If the first number in the sequence is $1$ , then second number must be $0$ . In this case, starting from the third position, we can build $f (n - 2)$ sequences.

We have Fibonacci numbers with base cases $f (1) = 2, f (2) = 3$ .

Let $f (n)$ denote the number of valid sequences of length $n$ . consisting of $0$ s and $1$ s. Consider constructing such a sequence based on its first element.

If the first element is $0$ , then the remaining part of the sequence can be any valid sequence of length $n - 1$ . Therefore, there are $f (n - 1)$ such sequences.

If the first element is $1$ , consider the possible continuations:

If the second element is $0$ , then the remaining $n - 2$ positions can form any valid sequence of length $n - 2$ , giving $f (n - 2)$ possibilities;
If the second element is $1$ , then to avoid having three consecutive $1$ s, the third element must be $0$ . The remaining $n - 3$ positions can then form any valid sequence of length $n - 3$ , giving $f (n - 3)$ possibilities.

Thus, we obtain the following recurrence relation:

f (n) = f (n - 1) + f (n - 2) + f (n - 3)

It remains to determine the base cases:

$f (1) = 2$ , since there are two sequences of length $1$ : $0$ and $1$ .
$f (2) = 4$ , since there are four sequences of length $2$ : $00, 01, 10$ and $11$ .
$f (3) = 7$ , since there are seven sequences of length $3$ : $000, 001, 010, 011, 100, 101$ and $110$ .

Example

Declare an array $f$ to store the values $f (1), f (2), ..., f (n)$ .

int f[100010];

Read the input value $n$ .

scanf("%d",&n);

Initialize the base values of the array.

f[1] = 2; f[2] = 4; f[3] = 7;

Compute the values $f (i)$ using the recurrence relation. Perform all calculations modulo $12345$ .

for(i = 4; i <= n; i++)
  f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;

Print the answer.

printf("%d\n",f[n]);

Algorithm implementation – recursion + memorization

Declare an array $d p$ to store intermediate results:

$d p [i]$ will store the value $f (i)$

int dp[100001];

Implement the function $f (n)$ , which returns the number of valid sequences of $0$ s and $1$ s of length $n$ . Use memoization.

int f(int n)
{
  if (n == 1) return 2;
  if (n == 2) return 4;
  if (n == 3) return 7;
  if (dp[n] != -1) return dp[n];
  return dp[n] = (f(n-1) + f(n-2) + f(n-3)) % 12345;
}

The main part of the program. Read the input value $n$ .

scanf("%d",&n);

Initialize the $d p$ array.

memset(dp,-1,sizeof(dp));

Compute and print the value $f (n)$ .

printf("%d\n",f(n));

It is known that Fibonacci numbers satisfy the following identity:

GC D (F_{n}, F_{m}) = F_{GC D (n, m)}

This means that the problem reduces to computing the $k$ -th Fibonacci number modulo $1 0^{8}$ , where

k = GC D (n, m)

Since $n, m \leq 1 0^{18}$ , we have $k \leq 1 0^{18}$ . Therefore, it is necessary to compute the value of $F_{k} m o d 1 0^{8}$ in $O (l o g_{2} k)$ time.

Theorem. To efficiently compute Fibonacci numbers, it is convenient to use matrix exponentiation. It is known that:

(1110)^{k} = (F_{k + 1} F_{k} F_{k} F_{k - 1})

Base case. For $k = 1$ , we have:

(1110) = (F_{2} F_{1} F_{1} F_{0})

which is true since $F_{0} = 0, F_{1} = 1, F_{2} = 1$ .

Inductive step. Assume that the formula holds for $k$ . Then, for $k + 1$ :

(1110)^{k + 1} = (F_{k + 1} F_{k} F_{k} F_{k - 1}) (1110) = (F_{k + 1} + F_{k} F_{k} + F_{k - 1} F_{k + 1} F_{k}) = (F_{k + 2} F_{k + 1} F_{k + 1} F_{k})

Thus, the formula is valid for all $k \geq 1$ .

It remains to implement raising a matrix to the power $k$ using fast exponentiation in $O (l o g_{2} k)$ time.

Example

Fibonacci numbers are defined as follows:

Let's compute the Fibonacci numbers using matrix exponentiation:

(1110)^{2} = (1110) \cdot (1110) = (2111) = (F_{3} F_{2} F_{2} F_{1})

(1110)^{4} = (2111)^{2} = (2111) \cdot (2111) = (5332) = (F_{5} F_{4} F_{4} F_{3})

(1110)^{8} = (5332)^{2} = (5332) \cdot (5332) = (34212113) = (F_{9} F_{8} F_{8} F_{7})

Let us declare the constant $MO D$ , modulo which all computations will be performed.

#define MOD 100000000

The function gcd computes the greatest common divisor of two numbers $a$ and $b$ .

long long gcd(long long a, long long b)
{
  return (!b) ? a : gcd(b, a % b);
}

Let us declare a Matrix class and write its constructor.

class Matrix
{
public:
  long long a, b, c, d;
  Matrix(long long a = 1, long long b = 0, 
         long long c = 0, long long d = 1) 
  {
    this->a = a; this->b = b;
    this->c = c; this->d = d;
  }

Let us overload the matrix multiplication operator. All computations are performed modulo $MO D = 1 0^{8}$ .

  Matrix operator* (const Matrix &x)
  {
    Matrix res;
    res.a = (a * x.a + b * x.c) % MOD;
    res.b = (a * x.b + b * x.d) % MOD;
    res.c = (c * x.a + d * x.c) % MOD;
    res.d = (c * x.b + d * x.d) % MOD;
    return res;
  }

Next, overload the operator for raising a matrix to the power $n$ . The time complexity of the algorithm is $O (l o g_{2} n)$ .

  Matrix operator^ (long long n)
  {
    Matrix x(*this);
    if (n == 0) return Matrix();
    if (n & 1) return x * (x ^ (n - 1));
    return (x * x) ^ (n/2);
  }
};

The function fib returns the $n$ -th Fibonacci number $F_{n}$ modulo $1 0^{8}$ .

long long fib(long long n)
{
  Matrix res(1,1,1,0);
  res = res ^ n;
  return res.b;
}

The main part of the program. Read the input data, compute, and print the value of $F_{GC D (n, m)}$ .

while(scanf("%lld %lld",&n,&m) == 2)
{
  d = gcd(n,m);
  printf("%lld\n",fib(d));
}

Algorithm implementation – functions

Let us declare the constant $MO D$ , modulo which all computations will be performed.

#define MOD 100000000

The function gcd computes the greatest common divisor of two numbers $a$ and $b$ .

long long gcd(long long a, long long b)
{
  return (!b) ? a : gcd(b, a % b);
}

Declare the Matrix structure — a $2 \times 2$ matrix. By default, the identity matrix is created, which is convenient for exponentiation.

struct Matrix 
{
  long long a, b, c, d;
  Matrix(long long a_ = 1, long long b_ = 0,
         long long c_ = 0, long long d_ = 1)
         : a(a_), b(b_), c(c_), d(d_) {}
};

The function multiply multiplies two $2 \times 2$ matrices using the standard formula.

Matrix multiply(Matrix &x, Matrix &y) 
{
  return Matrix(
    (x.a * y.a + x.b * y.c) % MOD,
    (x.a * y.b + x.b * y.d) % MOD,
    (x.c * y.a + x.d * y.c) % MOD,
    (x.c * y.b + x.d * y.d) % MOD
  );
}

The function power implements binary exponentiation of the matrix $ba se$ to the power $e x p$ .

Matrix power(Matrix base, long long exp) 
{
  Matrix result;
  while (exp > 0)
  {
    if (exp & 1)
      result = multiply(result, base);
    base = multiply(base, base);
    exp >>= 1;
  }
  return result;
}

The function fib computes the $n$ -th Fibonacci number modulo $1 0^{8}$ using the matrix method.

long long fib(long long n) 
{
  if (n == 0) return 0;
  Matrix m(1, 1, 1, 0);
  Matrix res = power(m, n);
  return res.b; // F(n)
}

The main part of the program. Read the input data, compute, and print the value of $F_{GC D (n, m)}$ .

while (scanf("%lld %lld", &n, &m) == 2) 
{
  d = gcd(n, m);
  printf("%lld\n", fib(d));
}

Algorithm implementation – memoization

The following identity is known for Fibonacci numbers:

F_{n + m} = F_{m} \cdot F_{n + 1} + F_{m - 1} \cdot F_{n}

From it, the following special cases directly follow:

if $m = n$ , then $F_{2 n} = F_{n} \cdot F_{n + 1} + F_{n - 1} \cdot F_{n}$ .
if $m = n + 1$ , then $F_{2 n + 1} = F_{n + 1} \cdot F_{n + 1} + F_{n} \cdot F_{n}$ .

These formulas allow Fibonacci numbers to be computed using a "divide and conquer" approach, reducing the computation of $F_{n}$ to values with indices approximately half as large.

The base cases are handled separately:

F_{0} = 0, F_{1} = F_{2} = 1

With this approach, the recursion depth is proportional to $l o g_{2} n$ , and the time complexity of the algorithm is $O (l o g_{2} n)$ .

Declare the constant $MO D$ , modulo which all computations will be performed.

#define MOD 100000000

Declare a variable $F$ of type map to store (memoize) the Fibonacci numbers that have already been computed.

map<long long, long long> F;

The function gcd computes the greatest common divisor of two numbers $a$ and $b$ .

long long gcd(long long a, long long b)
{
  return (!b) ? a : gcd(b,a % b);
}

The function fib computes the $n$ -th Fibonacci number modulo $1 0^{8}$ .

long long fib(long long n)
{

The base cases are handled separately.

  if (n == 0) return 0;
  if (n == 1) return 1;
  if (n == 2) return 1;

If the value of $F_{n}$ has already been computed and stored in $F$ , it is returned immediately without recomputation.

  if (F[n]) return F[n];

Next, we use the decomposition of the number $n$ into:

$n = 2 k + 1$ — odd case: $F_{n} = F_{k}^{2} + F_{k + 1}^{2}$ .
$n = 2 k$ — even case: $F_{n} = F_{k} \cdot F_{k + 1} + F_{k - 1} \cdot F_{k}$ .

  long long k = n / 2;

Store and return the result.

  if (n % 2 == 1) // n = 2*k + 1
    return F[n] = (fib(k) * fib(k) + fib(k+1) * fib(k+1)) % MOD;
  else // n = 2*k
    return F[n] = (fib(k) * fib(k+1) + fib(k-1) * fib(k)) % MOD;
}

The main part of the program. Read the input data, compute, and print the value of $F_{GC D (n, m)}$ .

while(scanf("%lld %lld",&a,&b) == 2)
{
  d = gcd(a,b);
  printf("%lld\n",fib(d));
}

Theorem. For the Fibonacci numbers, the following formula holds:

S (n) = F (0) + F (1) + ... + F (n) = F (n + 2) - 1

Proof. We prove the statement by induction.

Base case. For $n = 0$ we have:

F (0) = F (2) - 1,

That is, $0 = 1 - 1$ , which is true.

Inductive step. Assume that:

S (n) = F (n + 2) - 1

Then:

S (n + 1) = F (0) + F (1) + ... + F (n) + F (n + 1) = (F (n + 2) - 1) + F (n + 1) = F (n + 3) - 1,

which completes the proof

Then the desired sum

S = F (a) + F (a + 1) + ... + F (b)

can be computed as

S = S (b) - S (a - 1)

Computing Fibonacci numbers using Binet's formula

Consider the generating function for the Fibonacci numbers ( $F_{0} = 0, F_{1} = 1$ ):

G (x) = n = 0 \sum \infty F_{n} x^{n} = F_{0} + F_{1} x + n = 2 \sum \infty F_{n} x^{n} = F_{0} + F_{1} x + n = 2 \sum \infty (F_{n - 1} + F_{n - 2}) x^{n} = x + n = 2 \sum \infty F_{n - 1} x^{n} + n = 2 \sum \infty F_{n - 2} x^{n} = x + x n = 1 \sum \infty F_{n} x^{n} + x^{2} n = 0 \sum \infty F_{n} x^{n} = x + x G (x) + x^{2} G (x)

From this it follows that:

G (x) (1 - x - x^{2}) = x, G (x) = \frac{x}{1 - x - x ^{2}}

Let us decompose the generating function into partial fractions. First, find the roots of the denominator:

1 - x - x^{2} = (1 - φ x) (1 - ψ x),

where

φ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}

Now represent the generating function as:

\frac{x}{1 - x - x ^{2}} = \frac{A}{1 - φ x} + \frac{B}{1 - ψ x}

Solving the system, we obtain:

A = \frac{1}{5}, B = - \frac{1}{5}

Taking into account that

\frac{1}{1 - r x} = n = 0 \sum \infty r^{n} x^{n},

the generating function can be rewritten as:

G (x) = \frac{1}{5} (\frac{1}{1 - φ x} + \frac{1}{1 - ψ x}) = \frac{1}{5} n = 0 \sum \infty (φ^{n} - ψ^{n}) x^{n}

But since

G (x) = n = 0 \sum \infty F_{n} x^{n}

equating the coefficients of $x^{n}$ gives:

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5} = \frac{1}{5} ((\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}) = \frac{( 1 + 5 ) ^{n} - ( 1 - 5 ) ^{n}}{2 ^{n} 5}

Computing Fibonacci Numbers Using an Identity

For the Fibonacci numbers, the following identity is known:

F_{n + m} = F_{m} \cdot F_{n + 1} + F_{m - 1} \cdot F_{n}

From it, the following special cases follow directly:

if $m = n$ , then $F_{2 n} = F_{n} \cdot F_{n + 1} + F_{n - 1} \cdot F_{n}$
if $m = n + 1$ , then $F_{2 n + 1} = F_{n + 1} \cdot F_{n + 1} + F_{n} \cdot F_{n}$

These formulas make it possible to compute Fibonacci numbers using a divide-and-conquer approach, reducing the computation of $F_{n}$ to values with indices approximately half as large.

The base cases are handled separately:

F_{0} = 0, F_{1} = F_{2} = 1

With this approach, the recursion depth is proportional to $l o g_{2} n$ , and the time complexity of the algorithm is $O (l o g_{2} n)$ .

Example

Let us compute some Fibonacci numbers using Binet’s formula, working in the extended field $Z_{p} (5)$ with a large modulus $p$ .

F_{2} = \frac{1}{5} (\frac{1 + 5}{2})^{2} - (\frac{1 - 5}{2})^{2} = \frac{( 1 + 5 ) ^{2} - ( 1 - 5 ) ^{2}}{2 ^{2} 5} = \frac{( 6 + 2 5 ) - ( 6 - 2 5 )}{2 ^{2} 5} = \frac{4 5}{4 5} = 1 F_{3} = \frac{1}{5} (\frac{1 + 5}{2})^{3} - (\frac{1 - 5}{2})^{3} = \frac{( 1 + 5 ) ^{3} - ( 1 - 5 ) ^{3}}{2 ^{3} 5} = \frac{( 16 + 8 5 ) - ( 16 - 8 5 )}{2 ^{3} 5} = \frac{16 5}{8 5} = 2 F_{4} = \frac{1}{5} (\frac{1 + 5}{2})^{4} - (\frac{1 - 5}{2})^{4} = \frac{( 6 + 2 5 ) ^{2} - ( 6 - 2 5 ) ^{2}}{2 ^{4} 5} = \frac{( 56 + 24 5 ) - ( 56 - 24 5 )}{2 ^{4} 5} = \frac{48 5}{16 5} = 3

Let us illustrate the application of the formulas with an example:

if $m = n$ , then $F_{2 n} = F_{n} \cdot F_{n + 1} + F_{n - 1} \cdot F_{n}$
if $m = n + 1$ , then $F_{2 n + 1} = F_{n + 1} \cdot F_{n + 1} + F_{n} \cdot F_{n}$

F_{6} = F_{3} \cdot F_{4} + F_{2} \cdot F_{3} = 2 \cdot 3 + 1 \cdot 2 = 6 + 2 = 8, F_{7} = F_{4}^{2} + F_{3}^{2} = 3^{2} + 2^{2} = 9 + 4 = 13

Declare the constant $MO D$ , which will be used as the modulus for all computations.

#define MOD 1000000007

Declare a variable $f ib$ of type $ma p$ to store (memoize) already computed Fibonacci numbers.

map<long long, long long> fib;

The function f computes the $n$ -th Fibonacci number modulo $MO D$ .

long long f(long long n)
{
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (n == 2) return 1;

If the $n$ -th Fibonacci number has already been computed and stored in $f ib$ , it is returned immediately without recomputation.

  if (fib[n]) return fib[n];

Next, we decompose the number $n$ as follows:

$n = 2 k + 1$ — odd case: $F_{n} = F_{k}^{2} + F_{k + 1}^{2}$ .
$n = 2 k$ — even case: $F_{n} = F_{k} \cdot F_{k + 1} + F_{k - 1} \cdot F_{k}$ .

  long long k = n / 2;

Store the result and return it.

  if (n % 2 == 1) // n = 2*k + 1
    return fib[n] = (f(k) * f(k) + f(k + 1) * f(k + 1)) % MOD;
  else // n = 2*k
    return fib[n] = (f(k) * f(k + 1) + f(k - 1) * f(k)) % MOD;
}

The main part of the program. For each test case, read the input data and print the answer.

while (scanf("%lld %lld", &a, &b) == 2)
  printf("%lld\n", (f(b + 2) - f(a + 1) + MOD) % MOD);

Algorithm implementation – Binet's formula

Declare the constant $MO D$ , which will be used as the modulus for all computations.

#define MOD 1000000007

Declare the structure $N u m$ to store a number of the form $x + y 5$ .

struct Num
{
  long long x, y; // x + y*sqrt(c)
  Num(long long x_ = 0, long long y_ = 0) : x(x_), y(y_) {}
};

Implement multiplication in the field $Z_{p} (5)$ . The function mult returns the product of the numbers $a$ and $b$ .

Num mult(Num& a, Num& b)
{
  Num res;
  res.x = (a.x * b.x + 5 * a.y % MOD * b.y) % MOD;
   res.y = (a.x * b.y + a.y * b.x) % MOD;
   return res;
}

The function pow performs exponentiation of $ba s e^{n}$ , where $ba se$ is a number in the field $Z_{p} (5)$ .

Num pow(Num base, long long n)
{
  Num res = { 1, 0 }; // единица поля
  while (n > 0)
  {
    if (n & 1)
      res = mult(res, base);
    base = mult(base, base);
    n >>= 1;
  }
  return res;
}

The function modpow computes the value of $a^{k} m o d p$ .

long long pow(long long x, long long n)
{
  long long res = 1;
  x %= MOD;
  while (n > 0)
  {
    if (n & 1) res = res * x % MOD;
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}

The function fib computes the $n$ -th Fibonacci number.

long long fib(long long n)
{

Initialize the constants $φ = 1 + 5$ and $ψ = 1 - 5$ .

  Num phi(1, 1);
  Num psi(1, MOD - 1);

Compute the powers $A = φ^{n}$ and $B = ψ^{n}$ .

  Num A = pow(phi, n);
  Num B = pow(psi, n);

Since

F_{n} = \frac{1}{5} ((\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}) = \frac{( 1 + 5 ) ^{n} - ( 1 - 5 ) ^{n}}{2 ^{n} 5} = \frac{( A _{x} + A _{y} 5 ) - ( B _{x} + B _{y} 5 )}{2 ^{n} 5},

compute the numerator and denominator separately.

Note that $A_{x} = B_{x}$ (so $A_{x} - B_{x} = 0$ ), and the coefficient of $5$ in the numerator is $A_{y} - B_{y}$ .

  long long numerator = (A.y - B.y + MOD) % MOD;

Compute $2^{n}$ in the denominator.

  long long denom = pow(2, n);

Both the numerator and the denominator contain a factor of $5$ . Cancel this factor, leaving the result to be computed as:

(A_{y} - B_{y}) \cdot (2^{n})^{- 1} = n u m er a t or \cdot d e n o m^{- 1}

  long long denom_inv = pow(denom, MOD - 2);
  return numerator * denom_inv % MOD;
}

The main part of the program. For each test case, read the input data and print the answer.

while (scanf("%lld %lld", &a, &b) == 2)
  printf("%lld\n", (fib(b + 2) - fib(a + 1) + MOD) % MOD);

Let $g (n)$ be the number of ways to deal cards to $n$ teachers arranged in a line (the first and the last are not considered adjacent). This problem is equivalent to counting binary sequences of length $n$ consisting of $0$ s and $1$ s in which no two $1$ s are adjacent. The solution is given by the Fibonacci sequence defined by the following recurrence relation:

g (n) = ⎩ ⎨ ⎧ 2, n = 1, 3, n = 2, g (n - 1) + g (n - 2), n \geq 3.

Let $f (n)$ be the number of ways to deal cards to $n$ teachers seated in a circle.

If the first teacher does not receive an ace, then the remaining $n - 1$ teachers can be dealt aces in $g (n - 1)$ ways.
If the first teacher does receive an ace, then the second and the last teachers must not receive aces. In this case, the remaining $n - 3$ teachers can be dealt aces in $g (n - 3)$ ways.

Thus, we obtain the following relation:

f (n) = g (n - 1) + g (n - 3), i f n \geq 3

Example

For $n = 3$ , we need the value $g (0)$ . It can be found from the equality $g (0) + g (1) = g (2)$ , which gives

g (0) = g (2) - g (1) = 3 - 2 = 1

Therefore,

f (3) = g (2) + g (0) = 3 + 1 = 4

The base cases are as follows:

f (1) = 2 f (2) = 3

All containers in the world fall into two categories — with TNT and without.

Only a fool would place a TNT box on top of another TNT box. Since you're clearly not one of them (right?), you know very well that TNT explodes, especially if another TNT box is placed on top of it.

You find yourself in a room filled with a vast number of boxes of both types. Suddenly, a lift emerges from a hatch in the floor. Unfortunately, it is malfunctioning. It has decided to build a tower of $n$ boxes. To assess your chances of survival, you need to calculate the number of possible configurations in which nothing explodes.

By the way, think about it: what is a rational person like you doing in a room full of TNT?

Input. One integer $n (1 \leq n < 45)$ .

Output. Print the number of safe ways to build the tower.

Open problem

Number all the hexagons consecutively from left to right, top to bottom, as shown in the picture. In this numbering:

hexagons in the upper row have odd numbers;
hexagons in the lower row have even numbers.

If the upper row contains $n$ hexagons, the rightmost hexagon in the upper row will have number $2 n - 1$ .

Let $f (k)$ denote the number of ways to reach the hexagon numbered $k$ from the first hexagon. Since the bee needs to reach hexagon number $2 n - 1$ , the answer to the problem will be $f (2 n - 1)$ .

Now, let's consider the transitions between hexagons.

Let hexagon $k$ be in the upper row (an odd number). Then the bee can reach it either from hexagon $k - 2$ or from hexagon $k - 3$ . Therefore, for odd $k$ the following recurrence holds:

f (k) = f (k - 2) + f (k - 3)

Let hexagon $k$ be in the lower row (an even number). In this case, there is only one possible transition — from the previous hexagon:

f (k) = f (k - 1)

To implement the recursion, we need to set the initial values:

f (1) = 1, f (2) = 1, f (3) = 1

These can be easily verified directly from the bee's movement diagram.

Declare an array.

#define MAX 100
int fib[MAX];

Fill the elements of the $f ib$ array in accordance with the recurrence relation.

fib[0] = 0; fib[1] = 1; fib[2] = 1;
for (int i = 3; i < MAX; i++)
  if (i % 2 == 1) fib[i] = fib[i-2] + fib[i-3];
  else fib[i] = fib[i-1];

Read the value $n$ and print the answer $f (2 n - 1)$ .

scanf("%d",&n);
printf("%d\n",fib[2*n-1]);

Algorithm implementation – recursion + memorization

Declare an array.

int fib[90];

Implement a recursive function f using memoization.

int f(int n)
{
  if (n == 1) return 1;
  if (n == 2) return 1;
  if (n == 3) return 1;
  if (fib[n] != -1) return fib[n];
  if (n % 2 == 1) return fib[n] = f(n - 1) + f(n - 3);
  return fib[n] = f(n - 1);
}

The main part of the program. Read the input value $n$ .

scanf("%d",&n);

Compute and print the answer.

memset(fib,-1,sizeof(fib));
printf("%d\n",f(2*n-1));

Let:

$f_{r} (n)$ be the number of ways to color a flag with $n$ stripes, starting with a red stripe;
$f_{w} (n)$ be the number of ways to color a flag with $n$ stripes, starting with a white stripe;

Let’s consider how to compute the function $f_{r} (n)$ :

If the stripe following the red one is white, then the remaining flag of length $n - 1$ can be colored in $f_{w} (n - 1)$ ways;
If the stripe following the red one is blue, then the stripe after the blue one must be white. After that, the remaining flag of length $n - 2$ can be colored in $f_{w} (n - 2)$ ways;

Thus, we obtain the following equality:

f_{r} (n) = f_{w} (n - 1) + f_{w} (n - 2)

By analogous reasoning, we obtain:

f_{w} (n) = f_{r} (n - 1) + f_{r} (n - 2)

The initial conditions for the first recurrence are obvious:

$f r (1) = 1$ : A flag consisting of one stripe and starting with red can be colored in exactly one way — $R$ .
$f r (2) = 1$ : If the first stripe is red, then the second stripe cannot be red and cannot be blue (since a blue stripe must be placed between a red and a white stripe). Therefore, the second stripe must be white. The only possible arrangement is $R W$ .

Similarly,

f_{w} (1) = 1, f_{w} (2) = 1

Both functions $f_{r} (n)$ and $f_{w} (n)$ define Fibonacci numbers:

f_{r} (n) = F_{n}, f_{w} (n) = F_{n}

The coloring of the flag starts with the first stripe. It can be either red or white. Therefore, the total number of ways to color the flag is

f_{r} (n) + f_{w} (n) = 2 * F_{n}

Since $n < 65536$ , long arithmetic or Java programming language should be used.

import java.util.*;
import java.math.*;

public class Main
{
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    
    BigInteger a = new BigInteger("1"), b = a;
    for(int i = 0; i < n; i++)
    {
      BigInteger temp = a.add(b); 
      a = b;
      b = temp;
    }
    
    System.out.println(a);    
    con.close();
  }
}

Python implementation

Increase the limit to the required value (for example, $100, 000$ digits).

import sys
sys.set_int_max_str_digits(100000)

Read the input value $n$ .

n = int(input())

Process the base cases.

if n == 1:
  print(1)
elif n == 2:
  print(2)
else:

Compute the $n$ -th Fibonacci number.

  f1, f2 = 1, 2
  for i in range(n - 2):
    temp = f1 + f2
    f1, f2 = f2, temp

Print the answer.

  print(f2)

import java.util.*;
import java.math.*;

public class Main
{
  static BigInteger fib[] = new BigInteger[10001];
  
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    fib[2] = fib[1] = BigInteger.ONE;
    for(int i = 3; i < 10001; i++)
      fib[i] = fib[i-1].add(fib[i-2]);
    
    int tests = con.nextInt();
    for(int i = 0; i < tests; i++)
    {
      int n = con.nextInt();
      System.out.println(fib[n]);      
    }
    con.close();
  }
}

Java implementation – recursion with memoization

import java.util.*;
import java.math.*;

public class Main
{
  static BigInteger fib[] = new BigInteger[10001];    
  static BigInteger MUNIS1 = new BigInteger("-1");

  static BigInteger f(int n)
  {
    if (n <= 2) return BigInteger.ONE;
    if (fib[n].compareTo(MUNIS1) != 0) return fib[n];
    return fib[n] = f(n-1).add(f(n - 2));
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    for(int i = 0; i < 10001; i++) fib[i] = MUNIS1;
    int tests = con.nextInt();
    for(int i = 0; i < tests; i++)
    {
      int n = con.nextInt();
      System.out.println(f(n));      
    }
    con.close();
  }
}

Python implementation

Initialize the first two Fibonacci numbers: $F (1) = 1. F (2) = 1$ .

f1, f2 = 1, 1

Create a list $f ib$ to store the Fibonacci numbers. The value $F (0) = 0$ is added intentionally so that the indexing matches the problem statement.

fib = [0, f1, f2]

Compute the Fibonacci numbers up to $F (10002)$ .

for i in range(10000):
  add = f1 + f2
  fib.append(add)
  f1, f2 = f2, add

Read the number of test cases $t$ .

t = int(input())
for i in range(t):

Read the input value $n$ and print $F (n)$ .

  n = int(input())
  print(fib[n])

For the given integers $a, b, c, n, p$ , find the value of the expression:

(a + b c ​)^{n} m o d p

Print the result as two numbers $x$ and $y$ such that

x + y c = (a + b c ​)^{n} m o d p

Input. Five integers $a, b, c, n, p$ are given. It is known that:

$p < 1 0^{9}$ is a prime number,
$0 \leq a, b < p$ ,
$1 \leq c < p$ ,
$0 \leq n \leq 1 0^{18}$

Output. Print two integers $x$ and $y$ — the coefficients of $1$ and $c$ respectively, modulo $p$ .

Note. You should work in the extended field:

Z_{p} (c) = {x + y c ∣ x, y \in Z_{p}}

Operation rules:

Addition
$(x_{1} + y_{1} c) + (x_{2} + y_{2} c) = (x_{1} + x_{2}) + (y_{1} + y_{2}) c$
Multiplication
$(x_{1} + y_{1} c) \cdot (x_{2} + y_{2} c) = (x_{1} x_{2} + c y_{1} y_{2}) + (x_{1} y_{2} + x_{2} y_{1}) c$

All operations are performed modulo $p$ .

Examples. In the first example:

(2 + 5 ​)^{2} m o d 17 = 9 + 45

In the second example:

(3 + 25 ​)^{10} m o d 17 = 5 + 115

Open problem

All computations should be performed in the extended field:

Z_{p} (c) = {x + y c ∣ x, y \in Z_{p}}

Operation rules:

Addition

(x_{1} + y_{1} c) + (x_{2} + y_{2} c) = (x_{1} + x_{2}) + (y_{1} + y_{2}) c

Multiplication

(x_{1} + y_{1} c) \cdot (x_{2} + y_{2} c) = (x_{1} x_{2} + c y_{1} y_{2}) + (x_{1} y_{2} + x_{2} y_{1}) c

After defining the multiplication operation, elements of the field $Z_{p} (c)$ can be raised to a power using the standard binary exponentiation method in $O (l o g_{2} n)$ time. This makes it possible to compute $(a + b c)^{n} m o d p$ .

Example

In the first example

(2 + 5)^{2} m o d 17 = (4 + 45 + 5) m o d 17 = 9 + 45

Let us consider the second example:

(3 + 25)^{10} m o d 17

Let $x = 3 + 25$ . We'll compute its powers step by step:

x^{2} = (3 + 25)^{2} m o d 17 = (9 + 125 + 20) m o d 17 = 12 + 125 x^{4} = (12 + 125)^{2} m o d 17 = (144 + 2885 + 720) m o d 17 = 14 + 165 x^{8} = (14 + 165)^{2} m o d 17 = (196 + 4485 + 1280) m o d 17 = 14 + 65

Now we can compute the result:

x^{10} = x^{8} \cdot x^{2} = (14 + 65) (12 + 125) m o d 17 = (168 + 725 + 1685 + 360) m o d 17 = 1 + 25

Let us define a structure $N u m$ to store numbers of the form $x + y c$ .

struct Num
{
  long long x, y; // x + y*sqrt(c)
};

Let's implement multiplication in the field $Z_{p} (c)$ . The function mult returns the product of two numbers $a$ and $b$ .

Num mult(Num& a, Num& b)
{
  Num res;
  res.x = (a.x * b.x + c * a.y % p * b.y) % p;
  res.y = (a.x * b.y + a.y * b.x) % p;
  return res;
}

The function pow implements exponentiation, computing $ba s e^{n}$ , where $ba se$ is a number in the field $Z_{p} (c)$ .

Num pow(Num base, long long n)
{
  Num res = { 1, 0 };
  while (n > 0)
  {
    if (n & 1)
      res = mult(res, base);
    base = mult(base, base);
    n >>= 1;
  }
  return res;
}

The main part of the program. Read the input data.

scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &n, &p);

Initialize the starting number $s t a r t = a + b c$ .

Num start = { a % p, b % p };

Compute and print the answer $an s = s t a r t^{n} m o d p = (a + b c)^{n} m o d p$ .

Num ans = pow(start, n);
printf("%lld %lld\n", ans.x, ans.y);

For the given integers $a, b, c, n, p$ , compute the value of the sum:

i = 0 \sum n (a + b c ​)^{i} m o d p

Print the result as two numbers $x$ and $y$ such that

x + y c = i = 0 \sum n (a + b c ​)^{i} m o d p

Input. Five integers $a, b, c, n, p$ are given. It is known that:

$p < 1 0^{9}$ is a prime number,
$0 \leq a, b < p$ ,
$1 \leq c < p$ ,
$0 \leq n \leq 1 0^{9}$

Output. Print two integers $x$ and $y$ — the coefficients of $1$ and $c$ respectively, modulo $p$ .

Note. You should work in the extended field:

Z_{p} (c) = {x + y c ∣ x, y \in Z_{p}}

Operation rules:

Addition
$(x_{1} + y_{1} c) + (x_{2} + y_{2} c) = (x_{1} + x_{2}) + (y_{1} + y_{2}) c$
Multiplication
$(x_{1} + y_{1} c) \cdot (x_{2} + y_{2} c) = (x_{1} x_{2} + c y_{1} y_{2}) + (x_{1} y_{2} + x_{2} y_{1}) c$

All operations are performed modulo $p$ .

Examples. In the first example:

i = 0 \sum 2 (2 + 5 ​)^{i} m o d 17 = (1 + (2 + 5) + (9 + 45)) m o d 17 = 12 + 55

In the second example:

i = 0 \sum 10 (3 + 25 ​)^{i} m o d 17 = 15 + 65

Open problem

All computations should be performed in the extended field:

Z_{p} (c) = {x + y c ∣ x, y \in Z_{p}}

Operation rules:

Addition

(x_{1} + y_{1} c) + (x_{2} + y_{2} c) = (x_{1} + x_{2}) + (y_{1} + y_{2}) c

Multiplication

(x_{1} + y_{1} c) \cdot (x_{2} + y_{2} c) = (x_{1} x_{2} + c y_{1} y_{2}) + (x_{1} y_{2} + x_{2} y_{1}) c

Let $x = a + b c$ . Then the required sum is a finite geometric progression:

1 + x + x^{2} + x^{3} + ... + x^{n} = \frac{x ^{n + 1} - 1}{x - 1} = \frac{a}{b}

It remains to perform the division $a = x^{n + 1} - 1$ by $b = x - 1$ in the field $Z_{p} (c)$ :

\frac{a}{b} = \frac{a _{x} + a _{y} c}{b _{x} + b _{y} c} = \frac{( a _{x} + a _{y} c ) ( b _{x} - b _{y} c )}{( b _{x} + b _{y} c ) ( b _{x} - b _{y} c )} = \frac{( a _{x} + a _{y} c ) ( b _{x} - b _{y} c )}{b _{x}^{2} - b _{y}^{2} c} = (a_{x} + a_{y} c) (b_{x} - b_{y} c) (b_{x}^{2} - b_{y}^{2} c)^{- 1}

Example

In the first example

i = 0 \sum 2 (2 + 5)^{i} m o d 17 = (1 + (2 + 5) + (9 + 45)) m o d 17 = 12 + 55

Let's compute this example using the formula:

i = 0 \sum 2 (2 + 5)^{i} m o d 17 = \frac{( 2 + 5 ) ^{3} - 1}{( 2 + 5 ) - 1} = = \frac{( 8 + 12 5 + 30 + 5 5 ) - 1}{1 + 5} = \frac{37 + 17 5}{1 + 5} = \frac{3}{1 + 5} = \frac{3 ( 1 - 5 )}{( 1 + 5 ) ( 1 - 5 )} = \frac{3 ( 1 - 5 )}{- 4} = \frac{3 - 3 5}{13} = (3 - 35) \cdot 1 3^{- 1} = (3 - 35) \cdot 4 = 12 - 125 = 12 + 55

In the second example

i = 0 \sum 10 (3 + 25)^{i} m o d 17 = 15 + 65

The function modpow computes the value $a^{k} m o d p$ .

long long modpow(long long a, long long k, long long p)
{
  long long res = 1;
  a %= p;
  while (k)
  {
    if (k & 1) res = res * a % p;
    a = a * a % p;
    k >>= 1;
  }
  return res;
}

Let's define a structure $N u m$ to store numbers of the form $x + y c$ .

struct Num
{
  long long x, y; // x + y*sqrt(c)
};

Let's implement addition in the field $Z_{p} (c)$ . The function add returns the sum of two numbers $a$ and $b$ .

Num add(Num& a, Num& b)
{
  Num res;
  res.x = (a.x + b.x) % p;
  res.y = (a.y + b.y) % p;
  return res;
}

Let's implement subtraction in the field $Z_{p} (c)$ . The function sub returns the difference of two numbers $a$ and $b$ .

Num sub(Num& a, Num& b)
{
  Num res;
  res.x = (a.x - b.x + p) % p;
  res.y = (a.y - b.y + p) % p;
  return res;
}

Let's implement multiplication in the field $Z_{p} (c)$ . The function mult returns the product of two numbers $a$ and $b$ .

Num mult(Num& a, Num& b)
{
  Num res;
  res.x = (a.x * b.x + c * a.y % p * b.y) % p;
  res.y = (a.x * b.y + a.y * b.x) % p;
  return res;
}

The function pow implements exponentiation of $ba s e^{n}$ , where $ba se$ is an element of the field $Z_{p} (c)$ .

Num pow(Num base, long long n)
{
  Num res = { 1, 0 }; // единица поля
  while (n > 0)
  {
    if (n & 1)
      res = mult(res, base);
    base = mult(base, base);
    n >>= 1;
  }
  return res;
}

The function divide implements division in the field $Z_{p} (c)$ . It returns the quotient of the numbers $a$ and $b$ . The division is performed by multiplying by the conjugate:

\frac{a}{b} = \frac{a _{x} + a _{y} c}{b _{x} + b _{y} c} = \frac{( a _{x} + a _{y} c ) ( b _{x} - b _{y} c )}{( b _{x} + b _{y} c ) ( b _{x} - b _{y} c )} = \frac{( a _{x} + a _{y} c ) ( b _{x} - b _{y} c )}{b _{x}^{2} - b _{y}^{2} c} = (a_{x} + a_{y} c) (b_{x} - b_{y} c) (b_{x}^{2} - b_{y}^{2} c)^{- 1}

Num divide(Num& a, Num& b)
{

Let $co nj = b_{x} - b_{y} c$ .

  Num conj = { b.x, (p - b.y) % p };

Compute $n = (a_{x} + a_{y} c) (b_{x} - b_{y} c)$ .

  Num n = mult(a, conj);

Compute $d e n o m = b_{x}^{2} - b_{y}^{2} c$ .

  long long denom = 
    ((b.x * b.x) % p - ((b.y * b.y) % p * c) % p + p) % p;

Compute the multiplicative inverse and return $n / d e n o m = n \cdot d e n o m^{- 1}$ .

  long long inv_denom = modpow(denom, p - 2, p); // обратный элемент
  return Num((n.x * inv_denom) % p, (n.y * inv_denom) % p);
}

The main part of the program. Read the input data.

scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &n, &p);

Initialize the number $x = a + b c$ and the multiplicative identity of the field $o n e = 1 + 0 c$ .

Num x = { a % p, b % p };
Num one = { 1, 0 };

Compute $n u m = x^{n + 1} - 1$ , $d e n o m = x - 1$ .

Num num = pow(x, n + 1);
num = sub(num, one);
Num denom = sub(x, one);

Compute and print the answer $res = n u m / d e n o m = \frac{x ^{n + 1} - 1}{x - 1}$ .

Num res = divide(num, denom);
printf("%lld %lld\n", res.x, res.y);

Consider the Binet formula:

f_{i} = \frac{ϕ ^{i} - ψ ^{i}}{5}

where

ϕ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}

Then:

f_{i}^{k} = \frac{( ϕ ^{i} - ψ ^{i} ) ^{k}}{( 5 ) ^{k}} = \frac{1}{( 5 ) ^{k}} j = 0 \sum k (- 1)^{j} C_{k}^{j} ϕ^{i (k - j)} ψ^{ij} = \frac{1}{( 5 ) ^{k}} j = 0 \sum k (- 1)^{j} C_{k}^{j} (ϕ^{k - j} ψ^{j})^{i}

Now we sum over $i$ :

i = 1 \sum n f_{i}^{k} = \frac{1}{( 5 ) ^{k}} j = 0 \sum k (- 1)^{j} C_{k}^{j} i = 1 \sum n (ϕ^{k - j} ψ^{j})^{i}

The inner sum is an ordinary geometric progression:

i = 1 \sum n x^{i} = \frac{x ( x ^{n} - 1 )}{x - 1}, where x = ϕ^{k - j} ψ^{j}

To eliminate $5$ and avoid working with floating-point numbers, all computations will be performed in the extended field of the form $a + b 5$ modulo $1 0^{9} + 7$ .

Example

Consider summing powers with $k = 3$ .

f_{i}^{3} = \frac{( ϕ ^{i} - ψ ^{i} ) ^{3}}{( 5 ) ^{3}} = \frac{ϕ ^{3 i} - 3 ϕ ^{2 i} ψ ^{i} + 3 ϕ ^{i} ψ ^{2 i} - ψ ^{3 i}}{( 5 ) ^{3}}

Then the required sum is:

i = 1 \sum n f_{i}^{3} = \frac{\sum _{i = 1}^{n} ( ϕ ^{3} ) ^{i} - 3 \sum _{i = 1}^{n} ( ϕ ^{2} ψ ) ^{i} + 3 \sum _{i = 1}^{n} ( ϕ ψ ^{2} ) ^{i} - \sum _{i = 1}^{n} ( ψ ^{3} ) ^{i}}{( 5 ) ^{3}}

Declare a constant for the modulus $MO D$ .

#define MOD 1000000007

We'll store the values of binomial coefficients in the array $C nk$ .

vector<long long> Cnk;

To implement arithmetic in the field $Z_{MO D} [5]$ , define a structure $N u m$ . This structure represents numbers of the form $x + y 5$ .

struct Num
{
  long long x, y;
  Num(long long x = 0, long long y = 0) : x(x% MOD), y(y% MOD) {}
};

The function add implements addition in the field $Z_{MO D} [5]$ .

Num add(const Num& a, const Num& b)
{
  return Num((a.x + b.x) % MOD, (a.y + b.y) % MOD);
}

The function mult implements multiplication in the field $Z_{MO D} [5]$ .

Num mult(const Num& a, const Num& b)
{
  return Num(
    (a.x * b.x + 5 * a.y % MOD * b.y) % MOD,
    (a.x * b.y + a.y * b.x) % MOD
  );
}

The function pw implements binary exponentiation in the field $Z_{MO D} [5]$ , where the exponent $e x p$ is an integer.

Num pw(Num base, long long exp)
{
  Num res(1, 0);
  while (exp)
  {
    if (exp & 1) res = mult(res, base);
    base = mult(base, base);
    exp >>= 1;
  }
  return res;
}

The function pw implements fast binary exponentiation to compute $a^{b}$ modulo $MO D$ .

long long pw(long long a, long long b)
{
  long long res = 1;
  a %= MOD;
  while (b)
  {
    if (b & 1) res = (res * a) % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}

The function inv computes the multiplicative inverse of an element $a$ in the field $Z_{MO D} [5]$ .

a = x + y 5,

then its inverse element is given by

a^{- 1} = \frac{1}{x + y 5} = \frac{x - y 5}{x ^{2} - 5 y ^{2}}

Num inv(const Num& a)
{
  long long den = (a.x * a.x - 5 * a.y * a.y) % MOD;
  if (den < 0) den += MOD;

  long long invDen = pw(den, MOD - 2);

  return Num(
    a.x * invDen % MOD,
    (MOD - a.y) * invDen % MOD
  );
}

The function divide implements division in the field $Z_{MO D} [5]$ :

\frac{a}{b} = a \cdot b^{- 1}

Num divide(const Num& a, const Num& b)
{
  return mult(a, inv(b));
}

The main part of the program. Read the input data.

scanf("%lld %lld", &n, &k);

Compute the binomial coefficients $C_{k}^{0}, C_{k}^{1}, C_{k}^{2}, ..., C_{k}^{k}$ and store them in the array $C nk$ . Note that

C nk [i] = C_{k}^{i} = C_{k}^{i - 1} \cdot \frac{k - i + 1}{i}

Cnk.resize(k + 1);
Cnk[0] = 1;
for (i = 1; i <= k; i++)
{
  Cnk[i] = Cnk[i - 1] * (k - i + 1) % MOD;
  Cnk[i] = Cnk[i] * pw(i, MOD - 2) % MOD;
}

Compute $in v 2 = 2^{- 1} mod MO D = (MO D + 1) /2$ .

long long inv2 = (MOD + 1) / 2;

Initialize the constants: $p hi = ϕ = \frac{1 + 5}{2}$ and $p s i = ψ = \frac{1 - 5}{2}$ .

Num phi(inv2, inv2);
Num psi(inv2, MOD - inv2);

Compute $r a t i o = ψ / ϕ$ .

Num ratio = divide(psi, phi);

Initialize the constants $1$ and $- 1$ in the field $Z_{MO D} [5]$ .

Num one(1, 0);
Num minus_one(MOD - 1, 0);

The answer will be accumulated in the variable $res$ .

Num res(0, 0);

Initialize $t = ϕ^{k}$ . Then, in the loop, we will multiply this value by $r a t i o$ , obtaining

ϕ^{k}, ϕ^{k - 1} ψ, ϕ^{k - 2} ψ^{2}, ..., ϕ ψ^{k - 1}, ψ^{k}

Num t = pw(phi, k);

In the variable $res$ we compute the sum

i = 1 \sum n f_{i}^{k} = \frac{1}{( 5 ) ^{k}} j = 0 \sum k (- 1)^{j} C_{k}^{j} i = 1 \sum n (ϕ^{k - j} ψ^{j})^{i}

The required sum contains $k + 1$ terms. Therefore, we perform $k + 1$ iterations.

for (j = 0; j <= k; j++)
{
  Num term;

At this point $t = ϕ^{k - j} ψ^{j}$ . Compute the sum of the geometric progression:

t er m = i = 1 \sum n t^{i} = \frac{t ( t ^{n} - 1 )}{t - 1}

However, the case $t = 1$ should be handled separately, because the formula for the sum of a geometric progression contains division by $0$ . When $t = 1$ the sum takes the form: $1 + 1 + 1 + ... + 1$ ( $n$ times) and is equal to $n$ .

  if (t.x == 1 && t.y == 0)
    term = Num(n % MOD, 0);
  else
  {
    Num tn = pw(t, n);
    Num num = add(tn, minus_one);     // t^n - 1
    term = mult(t, num);              // t * (t^n - 1)
    Num den = add(t, minus_one);      // t - 1
    term = divide(term, den);         // t * (t^n - 1) / (t – 1)
  }

Compute $t er m = (- 1)^{j} C_{k}^{j} \cdot t er m$ .

  long long coef = Cnk[j];
  if (j & 1) coef = MOD - coef;

  term.x = term.x * coef % MOD;
  term.y = term.y * coef % MOD;

Add the next term $t er m$ to the result $res$ .

  res = add(res, term);

Multiply $t$ by $r a t i o$ , obtaining $t = ϕ^{k - j - 1} ψ^{j + 1}$ .

  t = mult(t, ratio);
}

It remains to divide $res$ by $(5)^{k}$ .

Num sqrt5(0, 1);
Num sqrt5k = pw(sqrt5, k);
res = divide(res, sqrt5k);

Print the answer.

printf("%lld\n", res.x);

List of problems

Comments

Nothing yet

Be the first one to start the conversation!

Loading

Just a moment, getting data from the server