Лихоманка Фібоначчі (Розбір)

Оскільки $n$ може досягати $1 0^{18}$ 10^{18}, перебирати числа Фібоначчі по одному неможливо. Матричний метод також не підходить: для суми $k$ -х степенів знадобилася б матриця розміру порядку $k$ , а $k$ може дорівнювати $1 0^{5}$ 10^5. Тому скористаємося явною формулою для чисел Фібоначчі — формулою Біне:

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

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

де

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

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

Числа $φ$ і $ψ$ є коренями рівняння $x^{2} = x + 1$ x^2 = x + 1, і за теоремою Вієта $φ ψ = - 1$ \varphi\psi = -1.

Розкриття степеня. Піднесемо формулу Біне до степеня $k$ і розкриємо дужки за біномом Ньютона:

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

Позначимо

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

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

Підсумуємо по $i$ від $1$ до $n$ і змінимо порядок підсумовування:

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}

Таким чином, сума з $n$ доданків звелася до суми з $k + 1$ k + 1 доданків.

Геометрична прогресія. Внутрішня сума є сумою геометричної прогресії зі знаменником $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}

Випадок $t = 1$ t = 1 дійсно виникає і потребує окремої обробки (інакше відбудеться ділення на нуль). Наприклад, якщо $k$ ділиться на $4$ , то при $j = k /2$ j = k / 2 отримуємо

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

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

Степінь $t^{n}$ t^n обчислюється бінарним піднесенням до степеня за $O (lo g n)$ O(\log n), тому кожен доданок знаходиться швидко навіть при $n = 1 0^{18}$ n = 10^{18}.

Послідовне обчислення знаменників. Не потрібно щоразу заново підносити $φ$ і $ψ$ до степеня для кожного $j$ . Сусідні знаменники пов'язані співвідношенням

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

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

тому достатньо один раз обчислити $t_{0} = φ^{k}$ t_0 = \varphi^k, а потім на кожній ітерації множити поточне значення на $ψ / φ$ .

Обчислення за модулем. Дійсна арифметика тут не підходить: потрібна точна відповідь за модулем $p = 1 0^{9} + 7$ p = 10^9 + 7. Працюватимемо з числами вигляду $a + b 5$ a + b\sqrt{5}, де $a$ і $b$ — лишки за модулем $p$ . Додавання і множення таких чисел виконуються за правилами

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

Числа вигляду $a + b 5$ a + b\sqrt{5} утворюють поле $Z_{p} [5]$ \mathbb{Z}_p[\sqrt{5}]. У цьому полі будь-який ненульовий елемент оборотний:

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

причому знаменник $a^{2} - 5 b^{2}$ a^2 - 5b^2 не дорівнює нулю за модулем $p$ . Це гарантує коректність усіх ділень у розв'язку. Ділення на $2$ у формулах для $φ$ і $ψ$ замінюється множенням на $2^{- 1} mod p = (p + 1) /2$ 2^{-1} \bmod p = (p + 1) / 2.

Обернений елемент до 2. Обернений до $2$ елемент за модулем $p$ — це таке число $x$ , що $2 x \equiv 1 (mod p)$ 2x \equiv 1 \pmod{p}.

Перевіримо, що $x = (p + 1) /2$ x = (p + 1) / 2 підходить:

$p = 1 0^{9} + 7$ p = 10^9 + 7 — непарне просте число, тому $p + 1$ p + 1 парне і $(p + 1) /2$ (p + 1) / 2 — ціле число. Воно менше за $p$ , тобто це звичайний лишок за модулем $p$ .
Помножимо його на $2$ : $2 \cdot (p + 1) /2 = p + 1 \equiv 1 (mod p)$ 2 \cdot (p + 1) / 2 = p + 1 \equiv 1 \pmod{p}.

Отже, $(p + 1) /2$ (p + 1) / 2 і є $2^{- 1} mod p$ 2^{-1} \bmod p.

Шукана сума є цілим числом, тому в підсумковому значенні $a + b 5$ a + b\sqrt{5} коефіцієнт $b$ обов'язково дорівнюватиме нулю, а відповіддю буде $a$ .

Приклад

Розглянемо перший приклад: $n = 4$ , $k = 1$ \boldsymbol{k = 1}. При $k = 1$ k = 1 формула набуває вигляду

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)

Обчислимо степені $φ$ , користуючись співвідношенням $φ^{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}

Їхня сума дорівнює $\frac{15 + 7 5}{2}$ \dfrac{15 + 7\sqrt{5}}{2}. Степені $ψ$ отримуються заміною $5$ \sqrt{5} на $- 5$ -\sqrt{5}, тому їхня сума дорівнює $\frac{15 - 7 5}{2}$ \dfrac{15 - 7\sqrt{5}}{2}. Отже,

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,

що збігається з відповіддю: $1 + 1 + 2 + 3 = 7$ 1 + 1 + 2 + 3 = 7.

Розглянемо приклад для $k = 3$ \boldsymbol{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 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}}

Знаменники прогресій дорівнюють (використовуємо $φ ψ = - 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

Тоді

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)

Кожна з чотирьох сум обчислюється за формулою геометричної прогресії. Перевіримо це при $n = 3$ n = 3. Степені $φ$ дорівнюють

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

Тоді

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}

Суми для $ψ$ отримуються заміною $5$ \sqrt{5} на $- 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}

Підставляємо знайдені значення:

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

Результат збігається з безпосереднім обчисленням:

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

Розглянемо приклад для $k = 4$ \boldsymbol{k = 4} (особливий випадок). Тут

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)

Середній доданок відповідає знаменнику $t_{2} = 1$ t_2 = 1: формула геометричної прогресії до нього незастосовна, а сума $1 + 1 + \dots + 1$ 1 + 1 + \ldots + 1 дорівнює $n$ . Саме цей випадок окремо обробляється в програмі. Наприклад, при $n = 3$ n = 3 отримуємо:

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

Реалізація алгоритму

Оголосимо константу модуля $M O D$ .

#define MOD 1000000007

У масиві $C nk$ зберігатимемо значення біноміальних коефіцієнтів.

vector<long long> Cnk;

Для реалізації арифметики в полі $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}] оголосимо структуру $N u m$ . Структура зберігає число вигляду $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) {}
};

Функція add реалізує додавання в полі $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);
}

Функція mult реалізує множення в полі $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++

Функція pw реалізує бінарне піднесення до степеня в полі $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}], де показник степеня $e x p$ є цілим числом.

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

Функція pw реалізує швидке бінарне піднесення до степеня $a^{b}$ a^b за модулем $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++

Функція inv обчислює обернений елемент до $a$ в полі $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}].

Якщо

a = x + y 5,

a = x + y \sqrt{5},

то оберненим до нього елементом буде

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

Функція divide реалізує ділення в полі $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));
}

Основна частина програми. Зчитуємо вхідні дані.

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

Обчислюємо біноміальні коефіцієнти $C_{k}^{0}, C_{k}^{1}, C_{k}^{2}, ..., C_{k}^{k}$ C_k^0, C_k^1, C_k^2, ..., C_k^k і заносимо їх у масив $C nk$ . Зазначимо, що

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

Обчислюємо $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;

Ініціалізуємо константи: $p hi = ϕ = \frac{1 + 5}{2}$ phi = \phi = \frac{1 + \sqrt{5}}{2} і $p s i = ψ = \frac{1 - 5}{2}$ psi = \psi = \frac{1 - \sqrt{5}}{2}.

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

Обчислюємо $r a t i o = ψ / ϕ$ ratio = \psi / \phi.

Num ratio = divide(psi, phi);

Ініціалізуємо константи $1$ і $- 1$ в полі $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}].

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

Відповідь накопичуватимемо у змінній $r es$ .

Num res(0, 0);

Ініціалізуємо $t = ϕ^{k}$ t = \phi^k. Далі в циклі множитимемо це значення на $r a t i o$ , отримуючи

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

У змінній $r es$ обчислюємо суму

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

Шукана сума містить $k + 1$ k + 1 доданків. Тому виконуємо $k + 1$ k + 1 ітерацій.

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

На даний момент $t = ϕ^{k - j} ψ^{j}$ t = \phi^{k-j} \psi^j. Обчислюємо суму геометричної прогресії:

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}

Однак випадок $t = 1$ t = 1 слід обробити окремо, оскільки у формулі суми геометричної прогресії буде ділення на $0$ . При $t = 1$ t = 1 сума набуває вигляду $1 + 1 + 1 + ... + 1$ 1 + 1 + 1 + ... + 1 ( $n$ разів) і дорівнює $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++

Обчислюємо $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;

Додаємо до результату $r es$ черговий доданок $t er m$ .

  res = add(res, term);

Множимо $t$ на $r a t i o$ , отримуємо $t = ϕ^{k - j - 1} ψ^{j + 1}$ t = \phi^{k-j-1} \psi^{j + 1}.

  t = mult(t, ratio);
}

Залишилося поділити $r es$ на $(5)^{k}$ (\sqrt{5})^k.

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

Виводимо відповідь.

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