Сколько 2014-значных чисел из 1,3,4,6,7,9 делится на 7

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[ex-math]

На последнем шаге можно попасть в отсутствующий остаток и единицы не будет. Надо последить за остатками во время рекурсии, это нетрудно.

[Sonic86]

Честно говоря по намекам я так и не понял, как эту задачу решали.
Я вчера смог так: сначала задачу надо максимально параметризовать, потом рассмотреть рекуррентное соотношение для суммы, выражающей число из цифр.
Пусть $M$ - множество цифр, $p$ - модуль, $r$ - остаток по модулю, $q$ - основание системы счисления, $a_k$ - последовательность цифр, $a_k \in M$, $b_n=\sum\limits_{k=0}^n q^ka_k$ (все параметры $b_n$ не пишу).
Рекуррентное соотношение: $b_n=b_{n-1}+q^na_n$.
Теперь рассмотрим распределение значений величины $b_n \pmod p$ - некий вектор размера $p$ (сумма компонент $=q^n$). Из него легко вычислить распределение значений $b_{n+1} \pmod p$ - это сумма $|M|$ векторов, полученных сдвигом $b_n \pmod p$ на понятно какую величину. Множество сдвигов каждый раз разное, но периодично с периодом, который делит $p-1$, если $p$ простое (если не простое, то то же самое, но картина посложнее). И все, можно просто решить рекуррентное соотношение. В исходном случае это довольно просто, а вот например при $p=5, M=\{0;1;3\}$ сразу везде лезут числа Фибоначчи.

Можно было бы еще поковырять, что там м.б. интересного в общем случае, но что-то ничего не придумал

[maxal]

Sonic86 в сообщении #1247134 писал(а):

Можно было бы еще поковырять, что там м.б. интересного в общем случае, но что-то ничего не придумал

Через мультисекцию производящей функции можно получить явную формулу.