Problem 377 [ProjectEuler.net]

 

 

 

[Условие задачи]
Решать задачу начнем с простого.
Для начала найдем $latex f(13)$. Это можно сделать несложным рекурсивно-комбинаторным алгоритмом, который оставим для самостоятельной проработки.
Итог: $latex f(13)=3835856884757$

Получить $latex f(169)$ тем же алгоритмом вряд ли получится.
Далее будет описан алгоритм, который может это сделать. Представленную логику можно применить для любой степени 13.

Введем интуитивно понятные термины:
Префикс длины L числа N – первые L цифр (старшие разряды) числа N.
Постфикс длины L числа N – последние L цифр (младшие разряды) числа N.
Сумма префикса/постфикса – сумма цифр, входящих в префикс/постфикс.
Под промежуточным числом будем понимать число, которое используется при подсчете значения $latex f({ 13 }^{ k })$, так например число 1121 является промежуточным для $latex f(5)$
По условию задачи нужно найти последние 9 цифр ответа. Минимальным постфиксом длины 9 промежуточного числа для $latex f(169)$ является 111111111, а максимальным - 999999999. Т.к. в условии оговорено, что в состав промежуточного числа не входит ноль, то можно сделать утверждение, что количество различных постфиксов длины 9 для промежуточных чисел будет ровно $latex { 9 }^{ 9 }=387 420 489$, а различных сумм заданных постфиксов $latex 81-9+1=73$.
Для фиксированного постфикса промежуточного числа найдем количество возможных префиксов. Пусть сумма постфикса равна $latex S$, тогда сумма префикса равна $latex 169-S$.
Пусть $latex G(N)$ – функция которая возвращает количество всевозможных префиксов, сумма цифр которых равна $latex N$. Остаточные знания нам навевают понятие Разбиение числа на слагаемые, но в нашем случае нужно использовать не разбиение, а Композицию числа на слагаемые.
В общем случае количество композиций числа $latex N$ на ненулевые слагаемые равно $latex { 2 }^{ N-1 }$, но это только в том случае, если нет ограничений на слагаемые. В нашем же случае каждое ненулевое слагаемое должно не превышать 9.
Для того, чтобы найти $latex G(N)$ вспомним старую задачу Зайчик. Если вникнуть, то можно увидеть, что в этой задаче как раз и ищется функция $latex G(N)$ с ограничением на максимальное слагаемое.
Получаем: $latex \displaystyle G(N)=\left\{\begin{matrix}1, N=0\\ 2^{N-1}, 1<=N<=9\\ \sum_{i=1}^{9}G(N-i), N>9\end{matrix}\right.$
Последняя формула выглядит весьма угрожающе. В интернетах находим, что $latex G(N)$ образует последовательность чисел, называемых Fibonacci 9-step numbers.
И вот наверное сейчас мы подошли к самому интересному. $latex G(169-9)$ мы еще сможем найти, а как быть если степень 13 будет велика. Нужен способ, который находит G(N) быстрее чем за O(N).
В книге “Программирование. Теоремы и задачи”(А.Шень) приводится пример, как можно найти N-ое число Фибоначчи за O(logN) с помощью быстрого возведения в степень начальной матрицы. Тот же принцип можно использовать и здесь. Приведу фрагмент, по которому можно понять общую логику:

1. typedef unsigned long long ULL;
2. const ULL OSN = (ULL)1e9;
3. const ULL BASE[SIZE][SIZE] = {
4.   {128, 64, 32, 16, 8, 4, 2, 1, 1},
5.   {64, 32, 16, 8, 4, 2, 1, 1, 0},
6.   {32, 16, 8, 4, 2, 1, 1, 0, 0},
7.   {16,  8, 4, 2, 1, 1, 0, 0, 0},
8.   {8,  4, 2, 1, 1, 0, 0, 0, 0},
9.   {4,  2, 1, 1, 0, 0, 0, 0, 0},
10.   {2,  1, 1, 0, 0, 0, 0, 0, 0},
11.   {1,  1, 0, 0, 0, 0, 0, 0, 0},
12.   {1,  0, 0, 0, 0, 0, 0, 0, 0}
13. };
14. const ULL A[SIZE][SIZE] = {
15.   {1, 1, 0, 0, 0, 0, 0, 0, 0},
16.   {1, 0, 1, 0, 0, 0, 0, 0, 0},
17.   {1, 0, 0, 1, 0, 0, 0, 0, 0},
18.   {1, 0, 0, 0, 1, 0, 0, 0, 0},
19.   {1, 0, 0, 0, 0, 1, 0, 0, 0},
20.   {1, 0, 0, 0, 0, 0, 1, 0, 0},
21.   {1, 0, 0, 0, 0, 0, 0, 1, 0},
22.   {1, 0, 0, 0, 0, 0, 0, 0, 1},
23.   {1, 0, 0, 0, 0, 0, 0, 0, 0}
24. };
25. const ULL E[SIZE][SIZE] = {
26.   {1, 0, 0, 0, 0, 0, 0, 0, 0},
27.   {0, 1, 0, 0, 0, 0, 0, 0, 0},
28.   {0, 0, 1, 0, 0, 0, 0, 0, 0},
29.   {0, 0, 0, 1, 0, 0, 0, 0, 0},
30.   {0, 0, 0, 0, 1, 0, 0, 0, 0},
31.   {0, 0, 0, 0, 0, 1, 0, 0, 0},
32.   {0, 0, 0, 0, 0, 0, 1, 0, 0},
33.   {0, 0, 0, 0, 0, 0, 0, 1, 0},
34.   {0, 0, 0, 0, 0, 0, 0, 0, 1}
35. };
36. ULL G(ULL n) {
37.   ULL res = 0;
38.   if (n <= 9) {
39.     res = _pow(2, n - 1);
40.   }
41.   else {
42.     matrix AN = E, cur = A;
43.     n -= SIZE - 2;
44.     while (n) {
45.       if (n & 1)
46.         AN = AN * cur;
47.       cur = cur * cur;
48.       n >>= 1;
49.     }
50.     matrix fin = matrix(BASE) * AN;
51.     res = fin.data[0][1];
52.   }
53.   return res;
54. }

* This source code was highlighted with Source Code Highlighter.

Все нужные кирпичики описаны. Теперь соберем их в общую картину. 
Последние 9 цифр суммы всех промежуточных чисел для $latex f(169)$ c фиксированным постфиксом можно найти по формуле: $latex postfix*G(169-sum(postfix))mod1e9$. Перебрав все возможные постфиксы можно найти и само значение $latex f(169)$. Для всех остальных степеней 13, как уже говорилось ранее, применима такая же логика. 
Можно предложить несколько схем, ускоряющих общие вычисления. Но их мы оставим для самостоятельной проработки.