Febbre di Fibonacci (Editoriale)

Poiché $n$ può arrivare fino a $1 0^{18}$ 10^{18}, non è possibile scorrere i numeri di Fibonacci uno alla volta. Nemmeno il metodo matriciale è adatto: per la somma delle potenze $k$ -esime servirebbe una matrice di dimensione dell'ordine di $k$ , e $k$ può arrivare fino a $1 0^{5}$ 10^5. Utilizziamo quindi una formula esplicita per i numeri di Fibonacci — la formula di Binet:

f_{i} = \frac{φ ^{i} - ψ ^{i}}{5},

f_i = \frac{\varphi^i - \psi^i}{\sqrt{5}},

dove

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

\varphi = \frac{1 + \sqrt{5}}{2}, \quad \psi = \frac{1 - \sqrt{5}}{2}

I numeri $φ$ e $ψ$ sono le radici dell'equazione $x^{2} = x + 1$ x^2 = x + 1 e, per le formule di Viète, $φ ψ = - 1$ \varphi\psi = -1.

Sviluppo della potenza. Eleviamo la formula di Binet alla potenza $k$ e sviluppiamo con il binomio di Newton:

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}

f_i^k = \frac{(\varphi^i - \psi^i)^k}{(\sqrt{5})^k} = \frac{1}{(\sqrt{5})^k}\sum_{j=0}^{k}(-1)^j C_k^j\, \varphi^{i(k-j)}\psi^{ij} = \frac{1}{(\sqrt{5})^k}\sum_{j=0}^{k}(-1)^j C_k^j\, \left(\varphi^{k-j}\psi^j\right)^i

Poniamo

t_{j} = φ^{k - j} ψ^{j}, j = 0, 1, \dots, k

t_j = \varphi^{k-j}\psi^j, \quad j = 0, 1, \ldots, k

Sommiamo su $i$ da $1$ a $n$ e scambiamo l'ordine di sommatoria:

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

S = \sum_{i=1}^{n} f_i^k = \frac{1}{(\sqrt{5})^k}\sum_{j=0}^{k}(-1)^j C_k^j \sum_{i=1}^{n} t_j^{\,i}

In questo modo la somma di $n$ termini si riduce a una somma di $k + 1$ k + 1 termini.

Progressione geometrica. La somma interna è la somma di una progressione geometrica di ragione $t = t_{j}$ t = t_j:

G (t) = i = 1 \sum n t^{i} = ⎩ ⎨ ⎧ \frac{t ( t ^{n} - 1 )}{t - 1}, n, t \neq = 1, t = 1

G(t) = \sum_{i=1}^{n} t^i = \begin{cases} \dfrac{t\,(t^n - 1)}{t - 1}, & t \neq 1, \\[2mm] n, & t = 1 \end{cases}

Il caso $t = 1$ t = 1 si presenta davvero e va gestito separatamente (altrimenti si avrebbe una divisione per zero). Ad esempio, se $k$ è divisibile per $4$ , allora per $j = k /2$ j = k / 2 si ottiene

t_{k /2} = (φ ψ)^{k /2} = (- 1)^{k /2} = 1

t_{k/2} = (\varphi\psi)^{k/2} = (-1)^{k/2} = 1

La potenza $t^{n}$ t^n si calcola con l'esponenziazione binaria in tempo $O (lo g n)$ O(\log n), quindi ogni termine si trova rapidamente anche per $n = 1 0^{18}$ n = 10^{18}.

Calcolo iterativo delle ragioni. Non è necessario elevare di nuovo $φ$ e $ψ$ a potenza per ogni $j$ . Le ragioni consecutive sono legate dalla relazione

t_{j + 1} = t_{j} \cdot \frac{ψ}{φ},

t_{j+1} = t_j \cdot \frac{\psi}{\varphi},

quindi basta calcolare una sola volta $t_{0} = φ^{k}$ t_0 = \varphi^k e poi, a ogni iterazione, moltiplicare il valore corrente per $ψ / φ$ .

Calcoli modulari. L'aritmetica in virgola mobile qui non è adatta: serve la risposta esatta modulo $p = 1 0^{9} + 7$ p = 10^9 + 7. Lavoreremo con numeri della forma $a + b 5$ a + b\sqrt{5}, dove $a$ e $b$ sono residui modulo $p$ . L'addizione e la moltiplicazione di tali numeri seguono le regole

(a + b 5) + (c + d 5) = (a + c) + (b + d) 5, (a + b 5) (c + d 5) = (a c + 5 b d) + (a d + b c) 5

(a + b\sqrt{5}) + (c + d\sqrt{5}) = (a + c) + (b + d)\sqrt{5}, \\ (a + b\sqrt{5})(c + d\sqrt{5}) = (ac + 5bd) + (ad + bc)\sqrt{5}

I numeri della forma $a + b 5$ a + b\sqrt{5} formano il campo $Z_{p} [5]$ \mathbb{Z}_p[\sqrt{5}]. In questo campo ogni elemento non nullo è invertibile:

(a + b 5)^{- 1} = \frac{a - b 5}{a ^{2} - 5 b ^{2}},

(a + b\sqrt{5})^{-1} = \frac{a - b\sqrt{5}}{a^2 - 5b^2},

dove il denominatore $a^{2} - 5 b^{2}$ a^2 - 5b^2 è diverso da zero modulo $p$ . Ciò garantisce la correttezza di tutte le divisioni nella soluzione. La divisione per $2$ nelle formule di $φ$ e $ψ$ viene sostituita dalla moltiplicazione per $2^{- 1} mod p = (p + 1) /2$ 2^{-1} \bmod p = (p + 1) / 2.

L'inverso di 2. L'inverso di $2$ modulo $p$ è un numero $x$ tale che $2 x \equiv 1 (mod p)$ 2x \equiv 1 \pmod{p}.

Verifichiamo che $x = (p + 1) /2$ x = (p + 1) / 2 soddisfa questa condizione:

$p = 1 0^{9} + 7$ p = 10^9 + 7 è un numero primo dispari, quindi $p + 1$ p + 1 è pari e $(p + 1) /2$ (p + 1) / 2 è un numero intero. Esso è minore di $p$ , cioè è un normale residuo modulo $p$ .
Moltiplichiamolo per $2$ : $2 \cdot (p + 1) /2 = p + 1 \equiv 1 (mod p)$ 2 \cdot (p + 1) / 2 = p + 1 \equiv 1 \pmod{p}.

Quindi $(p + 1) /2$ (p + 1) / 2 è proprio $2^{- 1} mod p$ 2^{-1} \bmod p.

La somma cercata è un numero intero, quindi nel valore finale $a + b 5$ a + b\sqrt{5} il coefficiente $b$ è necessariamente nullo e la risposta è $a$ .

Esempio

Consideriamo il primo esempio: $n = 4$ , $k = 1$ \boldsymbol{k = 1}. Per $k = 1$ k = 1 la formula diventa

S = \frac{1}{5} (i = 1 \sum 4 φ^{i} - i = 1 \sum 4 ψ^{i})

S = \frac{1}{\sqrt{5}}\left(\sum_{i=1}^{4}\varphi^i - \sum_{i=1}^{4}\psi^i\right)

Calcoliamo le potenze di $φ$ usando la relazione $φ^{2} = φ + 1$ \varphi^2 = \varphi + 1:

φ = \frac{1 + 5}{2}, φ^{2} = \frac{3 + 5}{2}, φ^{3} = \frac{4 + 2 5}{2}, φ^{4} = \frac{7 + 3 5}{2}

\varphi = \frac{1 + \sqrt{5}}{2}, \quad \varphi^2 = \frac{3 + \sqrt{5}}{2}, \quad \varphi^3 = \frac{4 + 2\sqrt{5}}{2}, \quad \varphi^4 = \frac{7 + 3\sqrt{5}}{2}

La loro somma è $\frac{15 + 7 5}{2}$ \dfrac{15 + 7\sqrt{5}}{2}. Le potenze di $ψ$ si ottengono sostituendo $5$ \sqrt{5} con $- 5$ -\sqrt{5}, quindi la loro somma è $\frac{15 - 7 5}{2}$ \dfrac{15 - 7\sqrt{5}}{2}. Pertanto,

S = \frac{1}{5} (\frac{15 + 7 5}{2} - \frac{15 - 7 5}{2}) = \frac{7 5}{5} = 7,

S = \frac{1}{\sqrt{5}}\left(\frac{15 + 7\sqrt{5}}{2} - \frac{15 - 7\sqrt{5}}{2}\right) = \frac{7\sqrt{5}}{\sqrt{5}} = 7,

il che coincide con la risposta: $1 + 1 + 2 + 3 = 7$ 1 + 1 + 2 + 3 = 7.

Consideriamo un esempio per $k = 3$ \boldsymbol{k = 3}. Sviluppiamo il cubo della differenza:

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

f_i^3 = \frac{(\varphi^i - \psi^i)^3}{(\sqrt{5})^3} = \frac{\varphi^{3i} - 3\varphi^{2i}\psi^i + 3\varphi^i\psi^{2i} - \psi^{3i}}{5\sqrt{5}}

Le ragioni delle progressioni sono (usiamo $φ ψ = - 1$ \varphi\psi = -1):

t_{0} = φ^{3}, t_{1} = φ^{2} ψ = - φ, t_{2} = φ ψ^{2} = - ψ, t_{3} = ψ^{3}

t_0 = \varphi^3, \quad t_1 = \varphi^2\psi = -\varphi, \quad t_2 = \varphi\psi^2 = -\psi, \quad t_3 = \psi^3

Allora

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

\sum_{i=1}^{n} f_i^3 = \frac{1}{5\sqrt{5}}\left(\sum_{i=1}^{n}(\varphi^3)^i - 3\sum_{i=1}^{n}(-\varphi)^i + 3\sum_{i=1}^{n}(-\psi)^i - \sum_{i=1}^{n}(\psi^3)^i\right)

Ciascuna delle quattro somme si calcola con la formula della progressione geometrica. Verifichiamolo per $n = 3$ n = 3. Le potenze di $φ$ sono

φ^{3} = 2 + 5, φ^{6} = 9 + 45, φ^{9} = 38 + 175

\varphi^3 = 2 + \sqrt{5}, \quad \varphi^6 = 9 + 4\sqrt{5}, \quad \varphi^9 = 38 + 17\sqrt{5}

Allora

i = 1 \sum 3 (φ^{3})^{i} = φ^{3} + φ^{6} + φ^{9} = (2 + 5) + (9 + 45) + (38 + 175) = 49 + 225, i = 1 \sum 3 (- φ)^{i} = - φ + φ^{2} - φ^{3} = \frac{- ( 1 + 5 ) + ( 3 + 5 ) - ( 4 + 2 5 )}{2} = - 1 - 5

\sum_{i=1}^{3}(\varphi^3)^i = \varphi^3 + \varphi^6 + \varphi^9 = (2 + \sqrt{5}) + (9 + 4\sqrt{5}) + (38 + 17\sqrt{5}) = 49 + 22\sqrt{5}, \\ \sum_{i=1}^{3}(-\varphi)^i = -\varphi + \varphi^2 - \varphi^3 = \frac{-(1 + \sqrt{5}) + (3 + \sqrt{5}) - (4 + 2\sqrt{5})}{2} = -1 - \sqrt{5}

Le somme per $ψ$ si ottengono sostituendo $5$ \sqrt{5} con $- 5$ -\sqrt{5}:

i = 1 \sum 3 (- ψ)^{i} = - 1 + 5, i = 1 \sum 3 (ψ^{3})^{i} = 49 - 225

\sum_{i=1}^{3}(-\psi)^i = -1 + \sqrt{5}, \quad \sum_{i=1}^{3}(\psi^3)^i = 49 - 22\sqrt{5}

Sostituendo i valori trovati:

i = 1 \sum 3 f_{i}^{3} = \frac{( 49 + 22 5 ) - 3 ( - 1 - 5 ) + 3 ( - 1 + 5 ) - ( 49 - 22 5 )}{5 5} = \frac{50 5}{5 5} = 10

\sum_{i=1}^{3} f_i^3 = \frac{(49 + 22\sqrt{5}) - 3(-1 - \sqrt{5}) + 3(-1 + \sqrt{5}) - (49 - 22\sqrt{5})}{5\sqrt{5}} = \frac{50\sqrt{5}}{5\sqrt{5}} = 10

Il risultato coincide con il calcolo diretto:

f_{1}^{3} + f_{2}^{3} + f_{3}^{3} = 1^{3} + 1^{3} + 2^{3} = 1 + 1 + 8 = 10

f_1^3 + f_2^3 + f_3^3 = 1^3 + 1^3 + 2^3 = 1 + 1 + 8 = 10

Consideriamo un esempio per $k = 4$ \boldsymbol{k = 4} (caso particolare). Qui

t_{0} = φ^{4}, t_{1} = φ^{3} ψ = - φ^{2}, t_{2} = φ^{2} ψ^{2} = 1, t_{3} = φ ψ^{3} = - ψ^{2}, t_{4} = ψ^{4}

t_0 = \varphi^4, \quad t_1 = \varphi^3\psi = -\varphi^2, \quad t_2 = \varphi^2\psi^2 = 1, \quad t_3 = \varphi\psi^3 = -\psi^2, \quad t_4 = \psi^4

i = 1 \sum n f_{i}^{4} = \frac{1}{25} (i = 1 \sum n (φ^{4})^{i} - 4 i = 1 \sum n (- φ^{2})^{i} + 6 n - 4 i = 1 \sum n (- ψ^{2})^{i} + i = 1 \sum n (ψ^{4})^{i})

\sum_{i=1}^{n} f_i^4 = \frac{1}{25}\Biggl(\sum_{i=1}^{n}(\varphi^4)^i - 4\sum_{i=1}^{n}(-\varphi^2)^i + 6n - 4\sum_{i=1}^{n}(-\psi^2)^i + \sum_{i=1}^{n}(\psi^4)^i\Biggr)

Il termine centrale corrisponde alla ragione $t_{2} = 1$ t_2 = 1: la formula della progressione geometrica non è applicabile e la somma $1 + 1 + \dots + 1$ 1 + 1 + \ldots + 1 vale $n$ . È proprio questo il caso gestito separatamente nel programma. Ad esempio, per $n = 3$ n = 3 si ottiene:

f_{1}^{4} + f_{2}^{4} + f_{3}^{4} = 1^{4} + 1^{4} + 2^{4} = 1 + 1 + 16 = 18

f_1^4 + f_2^4 + f_3^4 = 1^4 + 1^4 + 2^4 = 1 + 1 + 16 = 18

Implementazione dell'algoritmo

Dichiariamo una costante per il modulo $M O D$ .

#define MOD 1000000007

Memorizzeremo i valori dei coefficienti binomiali nell'array $C nk$ .

vector<long long> Cnk;

Per implementare l'aritmetica nel campo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}] definiamo la struttura $N u m$ . Questa struttura rappresenta i numeri della forma $x + y 5$ x + y \sqrt{5}.

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

La funzione add implementa l'addizione nel campo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}].

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

La funzione mult implementa la moltiplicazione nel campo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{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
  );
}

C++

La funzione pw implementa l'esponenziazione binaria nel campo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}], dove l'esponente $e x p$ è un numero intero.

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;
}

C++

La funzione pw implementa l'esponenziazione binaria veloce per calcolare $a^{b}$ a^b modulo $M O 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;
}

C++

La funzione inv calcola l'inverso moltiplicativo di un elemento $a$ nel campo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}].

a = x + y 5,

a = x + y \sqrt{5},

allora il suo inverso è dato da

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

a^{-1} = \frac{1}{x+y\sqrt{5}} = \frac{x-y\sqrt{5}}{x^2-5y^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
  );
}

C++

La funzione divide implementa la divisione nel campo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}]:

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

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

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

Parte principale del programma. Leggiamo i dati di input.

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

Calcoliamo i coefficienti binomiali $C_{k}^{0}, C_{k}^{1}, C_{k}^{2}, ..., C_{k}^{k}$ C_k^0, C_k^1, C_k^2, ..., C_k^k e li memorizziamo nell'array $C nk$ . Osserviamo che

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

Cnk[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;
}

C++

Calcoliamo $in v 2 = 2^{- 1} mod M O D = (M O D + 1) /2$ inv2 = 2^{-1} \mod MOD = (MOD + 1) / 2.

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

Inizializziamo le costanti: $p hi = ϕ = \frac{1 + 5}{2}$ phi = \phi = \frac{1 + \sqrt{5}}{2} e $p s i = ψ = \frac{1 - 5}{2}$ psi = \psi = \frac{1 - \sqrt{5}}{2}.

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

Calcoliamo $r a t i o = ψ / ϕ$ ratio = \psi / \phi.

Num ratio = divide(psi, phi);

Inizializziamo le costanti $1$ e $- 1$ nel campo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}].

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

La risposta verrà accumulata nella variabile $r es$ .

Num res(0, 0);

Inizializziamo $t = ϕ^{k}$ t = \phi^k. Successivamente, nel ciclo, moltiplicheremo questo valore per $r a t i o$ , ottenendo

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

\phi^k, \phi^{k-1}\psi, \phi^{k-2}\psi^2, ..., \phi\psi^{k-1}, \psi^k

Num t = pw(phi, k);

Nella variabile $r es$ calcoliamo la somma

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}

\sum_{i=1}^{n} f_i^k = \frac{1}{(\sqrt{5})^k} \sum_{j=0}^{k} (-1)^j C_k^j \sum_{i=1}^{n} \left(\phi^{k-j}\psi^j\right)^i

La somma cercata contiene $k + 1$ k + 1 termini. Pertanto eseguiamo $k + 1$ k + 1 iterazioni.

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

A questo punto $t = ϕ^{k - j} ψ^{j}$ t = \phi^{k-j} \psi^j. Calcoliamo la somma della progressione geometrica:

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

term = \sum_{i=1}^{n} t^i = \frac{t(t^n-1)}{t-1}

Tuttavia il caso $t = 1$ t = 1 va gestito separatamente, perché la formula della somma di una progressione geometrica contiene una divisione per $0$ . Per $t = 1$ t = 1 la somma assume la forma $1 + 1 + 1 + ... + 1$ 1 + 1 + 1 + ... + 1 ( $n$ volte) ed è uguale a $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)
  }

C++

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

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

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

Aggiungiamo il termine successivo $t er m$ al risultato $r es$ .

  res = add(res, term);

Moltiplichiamo $t$ per $r a t i o$ , ottenendo $t = ϕ^{k - j - 1} ψ^{j + 1}$ t = \phi^{k-j-1} \psi^{j + 1}.

  t = mult(t, ratio);
}

Resta da dividere $r es$ per $(5)^{k}$ (\sqrt{5})^k.

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

Stampiamo la risposta.

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