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, как уже говорилось ранее, применима такая же логика. 
Можно предложить несколько схем, ускоряющих общие вычисления. Но их мы оставим для самостоятельной проработки.

Расстановка знаков в арифметическом выражении

[Все темы по размещениям]

Задача: 155. Дешифровка выражения(contester.tsure.ru) [Условие]
Предварительные темы:    [Генерация всех размещений с повторениями рекурсивным способом]
                         [Генерация следующего размещения с повторениями]
                         [Подсчет арифметического выражения(обратная польская нотация)]
Дополнительная практика: Задачи для подсчета арифметического выражения (см. занятие 4 - архив)

Итак, имеется корректное арифметическое выражение вида (9?8)?(0?3)?2=-25, вместо знаков ? необходимо поставить одну из 4 операций +,-,*,/ так, чтобы выражение стало правильным. Если такого сделать нельзя, то нужно вывести “No solution.”. Для удобства гарантируется, что в левой части выражения все числа являются цифрами и отсутствуют унарные знаки. В правой же части может быть любое число по модулю не превышающее 10¹⁵.

Опять же для удобства рассмотрим более короткий пример: 2?(3?4)=-10
Алфавит знаков содержит четыре элемент: {+,-,/,*}.
Количество позиций в размещении(количество знаков ? в выражении): 2
Общее количество размещений: 4²=16

Сгенерируем все размещения с повторениями рекурсивным способом и получим все возможные комбинации исходного арифметического выражения:

1. 2+(3+4)=9
2. 2+(3-4)=1
3. 2+(3*4)=14
4. 2+(3/4)=2
5. 2-(3+4)=-5
6. 2-(3-4)=3
7. 2-(3*4)=-10
8. 2-(3/4)=2
9. 2*(3+4)=14
10. 2*(3-4)=-2
11. 2*(3*4)=24
12. 2*(3/4)=0
13. 2/(3+4)=0
14. 2/(3-4)=-2
15. 2/(3*4)=0
16. 2/(3/4)=NAN

* This source code was highlighted with Source Code Highlighter.

Значение NAN обозначает, что в выражении присутствует деление на ноль. Сам подсчет будем делать с помощью перевода в обратную польскую запись, подсчетом значения на лету.
Подсчет значения на лету можно сделать так:

1. string opers = "+-*/";
2. bool calc(INT &f, INT &s, char op, INT &res) {
3.   switch(op) {
4.     case '+' : res = f + s; return true;
5.     case '-' : res = f - s; return true;
6.     case '*' : res = f * s; return true;
7.     case '/' : if (s != 0) {
8.             res = f / s;
9.             return true;
10.           }
11.           return false;
12.   }
13.   return false;
14. }
15. bool calc_last (stack<INT> &val, stack<char> &oper) {
16.   INT s = val.top(); val.pop();
17.   INT f = val.top(); val.pop();
18.   INT r = -1;
19.   if (calc(f,s,oper.top(),r)) {
20.     val.push(r);
21.     oper.pop();
22.     return true;
23.   }
24.   return false;
25. }
26. int prior(char op) {
27.   switch(op) {
28.     case '+':
29.     case '-': return 0;
30.     case '*':
31.     case '/': return 1;
32.   }
33.   return -1;
34. }
35. bool is_num(char c) {
36.   return '0' <= c && c <= '9';
37. }
38. bool calc(const string &expr, INT &res) {
39.   stack<INT> val;
40.   stack<char> oper;
41.   for (int i=0;i<expr.size();++i) {
42.     if (is_num(expr[i]))
43.       val.push(expr[i] - '0');
44.     else if (expr[i] =='(')
45.       oper.push(expr[i]);
46.     else if (expr[i] == ')') {
47.       while (oper.top() != '(') {
48.         if (!calc_last(val, oper))
49.           return false;
50.       }
51.       oper.pop();
52.     }
53.     else { // expr[i] - операция
54.       while (!oper.empty()) {
55.         if (prior(oper.top()) >= prior(expr[i])) {
56.           if (!calc_last(val, oper))
57.             return false;
58.         }
59.         else break;
60.       }
61.       oper.push(expr[i]);
62.     }
63.   }
64.   while (!oper.empty()) {
65.     if (!calc_last(val,oper))
66.       return false;
67.   }
68.   res = val.top();
69.   return true;
70. }

* This source code was highlighted with Source Code Highlighter.

Исходный код: здесь

Отправляем в систему проверки на contester.tsure.ru и получаем вердикт: TLE9. =))
В худшем случае количество операций равно 10, значит общее количество генерируемых размещений будет 4¹⁰=1048576. Получается, что приведенный фрагмент кода подсчета значения выражения на лету будет запускаться более 1 млн. раз. Т.к. в данной задаче нам придется генерировать все размещения, то естественным путем оптимизации исходного решения – минимизировать количество построений обратной польской записи.
Рассмотрим несколько выражений и их обратные польские записи.

Номер     Выражение           Обратная польская запись
1         5*2+3-(7+2)/2       5 2 * 3 + 7 2 + 2 / -
2         5/2-3+(7-2)*2       5 2 / 3 – 7 2 – 2 * + 
3         5+2*3/(7*2)-2       5 2 3 * 7 2 * / + 2 -
4         5-2/3*(7/2)+2       5 2 3 / 7 2 / * – 2 +

Подсчет выражения по обратной польской записи осуществляется за 1 проход.
Т.к. соответствующие операции в выражениях 1 и 2 имеют одинаковые приоритеты, то для них получаются две обратные польские записи, которые можно считать подобными. Тоже самое можно наблюдать для выражений 3 и 4.
Две обратные польские записи назовем подобными, если соответствующие операции имеют одинаковый приоритет.
Все операции можно разбить на две группы:
1. С меньшим приоритетом(0) : + , -
2. С большим приоритетом(1) : * , /

Поэтому изначально можно сгенерировать до 2¹⁰=1024 размещений из приоритетов [0 и 1]. При этом, если на место операции выпадает 0 в размещении это говорит о том, что на ее место будут последовательно поставлены операции с нулевым приоритетом, т.е + или –.
Для выражений с одинаковыми размещениями приоритетов получаются подобные обратные польские записи.

Рассмотрим выражение:              5?2?3?(7?2)?2
Текущее размещение из приоритетов: {1, 0, 0, 0, 1} 
Обратная польская запись:          5 2 [1] 3 [0] 7 2 [0] 2 [1] [0], где [x] – операция с приоритетом x
Как можно заметить, текущая обратная польская запись соответствует 1 и 2 выражению из таблицы.

Далее подумаем, как можно перебрать конкретные знаки, с уже расставленными приоритетами операций.
Для текущего размещения R можно поставить в соответствие два размещения F и S.
При этом длина F равна количеству нулей в размещении R, а длина S – количеству единиц.
Элементы множества F будут состоять из операций с нулевым приоритетом, а S – из элементом с единичным приоритетом.

Номер   Выражение        R              F           S
1       5*2+3-(7+2)/2    {1,0,0,0,1}    {+,-,+}     {*,/}
2       5/2-3+(7-2)*2    {1,0,0,0,1}    {-,+,-}     {/,*}
3       5+2*3/(7*2)-2    {0,1,1,1,0}    {+,-}       {*,/,*}
4       5-2/3*(7/2)+2    {0,1,1,1,0}    {-,+}       {/,*,/}

Все вышеизложенную идею можно описать так. При этом получается, что в худшем случае придется генерировать 2¹⁰=1024 обратных польских записей вместо 4¹⁰=1048576. Благодаря этим преобразованием последнее решение уложилось в 1.5 секунды на сервере проверки.

В целях рефакторинга второй реализации можно скрестить генерацию размещений R и {F,S}.

Получение номера по размещению с повторениями

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Ранее мы научились генерировать размещение с повторениями по номеру. Как выяснилось вся задача свелась к переводу числа из 10-ой в k-ричную систему счисления. Текущая задача представляет собой обратное действие, следовательно будем переводить “число” из k-ричной в 10-ую систему.

Пусть размещение R = {2, 0, 2, 2, 1, 1, 1, 2}; n = 8; k = 3. Найдем номер этого размещения в лексикографическом порядке.
20221112₃=2*2187+0*729+2*243+2*81+1*27+1*9+1*3+2*1=4374+486+162+27+9+3+2=5063₁₀.

Учитывая, что нумерация всех размещений начинается с 0, получаем что размещение R имеет порядковый номер 5064.

1. typedef unsigned long long ULL;
2. ULL get_num_by_placement_rep(const vector<int> &cur, int n, int k) {
3.   ULL num = 0;
4.   ULL step = 1;
5.   for (int i=cur.size()-1;i>=0;--i) {
6.     num += cur[i] * step;
7.     step *= k;
8.   }
9.   return num;
10. }

* This source code was highlighted with Source Code Highlighter.

Генерация размещения с повторениями по номеру

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008
Практика: [82. Все строки длины n из k различных символов]

Как и ранее алфавитом будем считать первые k цифр начиная с нуля. Длина размещения равна n. Необходимо по номеру сгенерировать размещение с повторениями в лексикографическом порядке.
Для начала давайте рассмотрим все размещения с повторениями для n = 2 и k = 4:

1. 00
2. 01
3. 02
4. 03
5. 10
6. 11
7. 12
8. 13
9. 20
10. 21
11. 22
12. 23
13. 30
14. 31
15. 32
16. 33

Внимательный читатель возможно уже нашел закономерность между порядковым номером и размещением. Если внимательно присмотреться, то можно заметить, что размещения с повторениями это числа в k-ричной системе счисления и их перечисление в лексикографическом порядке полностью совпадает с их перечислением в порядке возрастания.
Проверим наше утверждение на размещении “31”: 31₄=4*3+1=13. Но размещение “31” соответствует 14 размещению. Номер 13 получился, потому что нумерация размещений изначально начинается с 0.
Данная логика отображена в следующей функции:

1. typedef unsigned long long ULL;
2. void gen_placement_rep_by_num(vector<int> &cur, ULL num, int n, int k) {
3.   cur.assign(n,0);
4.   int pos = n - 1;
5.   while (num) {
6.     cur[pos--] = num % k;
7.     num /= k;
8.   }
9. }

* This source code was highlighted with Source Code Highlighter.

Если значения n и k настолько велики, что не помещаются в unsigned long long необходимо использовать длинную арифметику.

Генерация следующего и предыдущего размещения с повторениями

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Пусть задан алфавит, состоящих из первых k цифр, начиная с 0. Также имеется текущее размещение с повторениями длины n. Найдем следующее размещение с повторениями в лексикографическом порядке.

R_i = {1, 5, 6, 4, 6}; n = 5; k = 7
R_i+1 = {1, 5, 6, 5, 0}

Для генерации следующего размещения будем пользоваться простым правилом:
Перебираем все элементы справа налево. Если текущий элемент равен k-1, тогда обнуляем его и переходим к элементу левее. В противном случае увеличиваем текущий элемент на 1 и заканчиваем генерацию. Если на текущем шаге были перебраны все элемента размещения, но не получилось инкрементировать никакой элемент, значит на текущем шаге мы работали с последним размещением для заданных n и k.

1. bool next_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos>=0 && r) {
5.     cur[pos]++;
6.     r = cur[pos] == k;
7.     if (r) cur[pos] = 0;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

Генерация предыдущего размещения делается по аналогичной схеме:

1. bool prev_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos >=0 && r) {
5.     cur[pos]--;
6.     r = cur[pos] == -1;
7.     if (r) cur[pos] = k-1;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.