Fiebre de Fibonacci (Editorial)

Como $n$ puede llegar a $1 0^{18}$ 10^{18}, es imposible recorrer los números de Fibonacci uno por uno. El método matricial tampoco sirve: para la suma de las potencias $k$ -ésimas haría falta una matriz de tamaño del orden de $k$ , y $k$ puede llegar a $1 0^{5}$ 10^5. Por lo tanto, utilizamos una fórmula explícita para los números de Fibonacci — la fórmula de Binet:

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

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

donde

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

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

Los números $φ$ y $ψ$ son las raíces de la ecuación $x^{2} = x + 1$ x^2 = x + 1 y, por las fórmulas de Vieta, $φ ψ = - 1$ \varphi\psi = -1.

Desarrollo de la potencia. Elevamos la fórmula de Binet a la potencia $k$ y la desarrollamos mediante el binomio de 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

Denotemos

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

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

Sumamos sobre $i$ desde $1$ hasta $n$ e intercambiamos el orden de la suma:

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}

Así, la suma de $n$ términos se reduce a una suma de $k + 1$ k + 1 términos.

Progresión geométrica. La suma interior es la suma de una progresión geométrica de razón $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}

El caso $t = 1$ t = 1 realmente se presenta y debe tratarse por separado (de lo contrario se produciría una división por cero). Por ejemplo, si $k$ es divisible por $4$ , entonces para $j = k /2$ j = k / 2 obtenemos

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

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

La potencia $t^{n}$ t^n se calcula mediante exponenciación binaria en tiempo $O (lo g n)$ O(\log n), por lo que cada término se obtiene rápidamente incluso para $n = 1 0^{18}$ n = 10^{18}.

Cálculo iterativo de las razones. No es necesario elevar $φ$ y $ψ$ a una potencia de nuevo para cada $j$ . Las razones consecutivas están relacionadas por

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

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

por lo que basta con calcular $t_{0} = φ^{k}$ t_0 = \varphi^k una sola vez y luego, en cada iteración, multiplicar el valor actual por $ψ / φ$ .

Cálculos modulares. La aritmética de punto flotante no sirve aquí: necesitamos la respuesta exacta módulo $p = 1 0^{9} + 7$ p = 10^9 + 7. Trabajaremos con números de la forma $a + b 5$ a + b\sqrt{5}, donde $a$ y $b$ son residuos módulo $p$ . La suma y la multiplicación de tales números siguen las reglas

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

Los números de la forma $a + b 5$ a + b\sqrt{5} forman el cuerpo $Z_{p} [5]$ \mathbb{Z}_p[\sqrt{5}]. En este cuerpo todo elemento no nulo es invertible:

(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},

donde el denominador $a^{2} - 5 b^{2}$ a^2 - 5b^2 no es cero módulo $p$ . Esto garantiza que todas las divisiones de la solución sean correctas. La división por $2$ en las fórmulas de $φ$ y $ψ$ se sustituye por la multiplicación por $2^{- 1} mod p = (p + 1) /2$ 2^{-1} \bmod p = (p + 1) / 2.

El inverso de 2. El inverso de $2$ módulo $p$ es un número $x$ tal que $2 x \equiv 1 (mod p)$ 2x \equiv 1 \pmod{p}.

Comprobemos que $x = (p + 1) /2$ x = (p + 1) / 2 cumple esta condición:

$p = 1 0^{9} + 7$ p = 10^9 + 7 es un número primo impar, por lo que $p + 1$ p + 1 es par y $(p + 1) /2$ (p + 1) / 2 es un número entero. Es menor que $p$ , es decir, es un residuo ordinario módulo $p$ .
Lo multiplicamos por $2$ : $2 \cdot (p + 1) /2 = p + 1 \equiv 1 (mod p)$ 2 \cdot (p + 1) / 2 = p + 1 \equiv 1 \pmod{p}.

Por lo tanto, $(p + 1) /2$ (p + 1) / 2 es exactamente $2^{- 1} mod p$ 2^{-1} \bmod p.

La suma buscada es un número entero, así que en el valor final $a + b 5$ a + b\sqrt{5} el coeficiente $b$ es necesariamente cero y la respuesta es $a$ .

Ejemplo

Consideremos el primer ejemplo: $n = 4$ , $k = 1$ \boldsymbol{k = 1}. Para $k = 1$ k = 1 la fórmula toma la forma

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)

Calculemos las potencias de $φ$ usando la relación $φ^{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}

Su suma es igual a $\frac{15 + 7 5}{2}$ \dfrac{15 + 7\sqrt{5}}{2}. Las potencias de $ψ$ se obtienen sustituyendo $5$ \sqrt{5} por $- 5$ -\sqrt{5}, por lo que su suma es igual a $\frac{15 - 7 5}{2}$ \dfrac{15 - 7\sqrt{5}}{2}. Por consiguiente,

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,

lo que coincide con la respuesta: $1 + 1 + 2 + 3 = 7$ 1 + 1 + 2 + 3 = 7.

Consideremos un ejemplo para $k = 3$ \boldsymbol{k = 3}. Desarrollamos el cubo de la diferencia:

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

Las razones de las progresiones son (usamos $φ ψ = - 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

Entonces

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)

Cada una de las cuatro sumas se calcula con la fórmula de la progresión geométrica. Comprobémoslo para $n = 3$ n = 3. Las potencias de $φ$ son

φ^{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}

Entonces

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}

Las sumas para $ψ$ se obtienen sustituyendo $5$ \sqrt{5} por $- 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}

Sustituyendo los valores obtenidos:

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

El resultado coincide con el cálculo directo:

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

Consideremos un ejemplo para $k = 4$ \boldsymbol{k = 4} (caso especial). Aquí

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)

El término central corresponde a la razón $t_{2} = 1$ t_2 = 1: la fórmula de la progresión geométrica no es aplicable y la suma $1 + 1 + \dots + 1$ 1 + 1 + \ldots + 1 es igual a $n$ . Precisamente este caso se trata por separado en el programa. Por ejemplo, para $n = 3$ n = 3 obtenemos:

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

Implementación del algoritmo

Declaramos una constante para el módulo $M O D$ .

#define MOD 1000000007

Guardaremos los valores de los coeficientes binomiales en el arreglo $C nk$ .

vector<long long> Cnk;

Para implementar la aritmética en el cuerpo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}], definimos la estructura $N u m$ . Esta estructura representa números de la 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 función add implementa la suma en el cuerpo $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 función mult implementa la multiplicación en el cuerpo $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 función pw implementa la exponenciación binaria en el cuerpo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}], donde el exponente $e x p$ es un número entero.

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 función pw implementa la exponenciación binaria rápida para calcular $a^{b}$ a^b módulo $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 función inv calcula el inverso multiplicativo de un elemento $a$ en el cuerpo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}].

a = x + y 5,

a = x + y \sqrt{5},

entonces su inverso es

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 función divide implementa la división en el cuerpo $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 principal del programa. Leemos los datos de entrada.

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

Calculamos los coeficientes binomiales $C_{k}^{0}, C_{k}^{1}, C_{k}^{2}, ..., C_{k}^{k}$ C_k^0, C_k^1, C_k^2, ..., C_k^k y los guardamos en el arreglo $C nk$ . Observemos que

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++

Calculamos $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;

Inicializamos las constantes: $p hi = ϕ = \frac{1 + 5}{2}$ phi = \phi = \frac{1 + \sqrt{5}}{2} y $p s i = ψ = \frac{1 - 5}{2}$ psi = \psi = \frac{1 - \sqrt{5}}{2}.

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

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

Num ratio = divide(psi, phi);

Inicializamos las constantes $1$ y $- 1$ en el cuerpo $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}].

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

La respuesta se acumulará en la variable $r es$ .

Num res(0, 0);

Inicializamos $t = ϕ^{k}$ t = \phi^k. Después, en el ciclo, multiplicaremos este valor por $r a t i o$ , obteniendo

ϕ^{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);

En la variable $r es$ calculamos la suma

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 suma buscada contiene $k + 1$ k + 1 términos. Por lo tanto, realizamos $k + 1$ k + 1 iteraciones.

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

En este momento $t = ϕ^{k - j} ψ^{j}$ t = \phi^{k-j} \psi^j. Calculamos la suma de la progresión geométrica:

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}

Sin embargo, el caso $t = 1$ t = 1 debe tratarse por separado, ya que la fórmula de la suma de una progresión geométrica contiene una división por $0$ . Cuando $t = 1$ t = 1 la suma toma la forma $1 + 1 + 1 + ... + 1$ 1 + 1 + 1 + ... + 1 ( $n$ veces) y es igual 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++

Calculamos $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;

Sumamos el siguiente término $t er m$ al resultado $r es$ .

  res = add(res, term);

Multiplicamos $t$ por $r a t i o$ y obtenemos $t = ϕ^{k - j - 1} ψ^{j + 1}$ t = \phi^{k-j-1} \psi^{j + 1}.

  t = mult(t, ratio);
}

Queda dividir $r es$ entre $(5)^{k}$ (\sqrt{5})^k.

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

Imprimimos la respuesta.

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