Задача: дна $n$ и $c$, найти кол-во последовательностей $A$ длины $n$ для которых выполняется:↵
↵
- $1\leq a_{i} \leq c$↵
- $\forall i \in {1,2,\ldots,n-1}: a_{i} | a_{i+1} $ ($a_{i+1}$ делится на $a_{i}$)↵
↵
(Да, да, задачка с открытки)↵
#### Крутой факт:↵
↵
- Пусть $ANS_{n,c}$ ответ для $n$, $c$↵
↵
- Пусть $A_{c} = ANS_{1,c},ANS_{2,c},ANS_{3,c},\ldots$↵
↵
Неожиданно, $A_{c}$ может быть описан многочленном $P_{c}$ степени $\lfloor{\log_2{c}}\rfloor$, то есть $P_{c}(X) = ANS_{X,c}$↵
↵
Откуда $\log_2$ всплывает? Непонятно.↵
↵
Вообщем-то, Пытаюсь найти закономерность в коэффициентах $P_{c}$ и у меня не получается. Заметил что <span style="white-space: nowrap;">(Пусть коэффициент при $x^i$ это $P_{c, i_{i}}$ )</span> $P_{c,i_{i}} = \frac{F(c,i)}{(\lfloor{\log_2{c}}\rfloor + i)!}$ где ${F(c,i)}$ Какая-то странная функция которую я не могу вычислить. <br><br>Прикрепил вычисленные коэффициенты для $1\leq c \leq 127$ и код для их вычисления, вдруг кто-то найдёт закономерность.↵
↵
↵
<spoiler summary="коэффициенты">[link](https://gist.github.com/brezhart/a9fb5a37139946dd8cb839ef9fd9c706)</spoiler>↵
↵
<spoiler summary="Код для вычисления коээфициентов">[link](https://gist.github.com/brezhart/a2ca9571494429805b4132445b585350)</spoiler>↵
↵
Если у кого-то есть информация по теме, буду рад услышать.↵
↵
[Ссылка на задачу с аткодера](https://atcoder.jp/contests/arc116/tasks/arc116_c) и [на моё решение](https://atcoder.jp/contests/arc116/submissions/29935374) которое использует факт про многочлен степени $\lfloor{\log_2{c}}\rfloor$↵
↵
↵
↵
- $1\leq a_{i} \leq c$↵
- $\forall i \in {1,2,\ldots,n-1}: a_{i} | a_{i+1} $ ($a_{i+1}$ делится на $a_{i}$)↵
↵
(Да, да, задачка с открытки)↵
#### Крутой факт:↵
↵
- Пусть $ANS_{n,c}$ ответ для $n$, $c$↵
↵
- Пусть $A_{c} = ANS_{1,c},ANS_{2,c},ANS_{3,c},\ldots$↵
↵
Неожиданно, $A_{c}$ может быть описан многочленном $P_{c}$ степени $\lfloor{\log_2{c}}\rfloor$, то есть $P_{c}(X) = ANS_{X,c}$↵
↵
Откуда $\log_2$ всплывает? Непонятно.↵
↵
Вообщем-то, Пытаюсь найти закономерность в коэффициентах $P_{c}$ и у меня не получается. Заметил что <span style="white-space: nowrap;">(Пусть коэффициент при $x^i$ это $P_{c
↵
↵
<spoiler summary="коэффициенты">[link](https://gist.github.com/brezhart/a9fb5a37139946dd8cb839ef9fd9c706)</spoiler>↵
↵
<spoiler summary="Код для вычисления коээфициентов">[link](https://gist.github.com/brezhart/a2ca9571494429805b4132445b585350)</spoiler>↵
↵
Если у кого-то есть информация по теме, буду рад услышать.↵
↵
[Ссылка на задачу с аткодера](https://atcoder.jp/contests/arc116/tasks/arc116_c) и [на моё решение](https://atcoder.jp/contests/arc116/submissions/29935374) которое использует факт про многочлен степени $\lfloor{\log_2{c}}\rfloor$↵
↵
↵
