Searching for a pattern
Разница между ru4 и ru5, 9 символ(ов) изменены
Задача: дна $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$↵


История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский brezhart 2022-03-09 22:29:51 9
ru5 Русский brezhart 2022-03-09 22:29:17 9
ru4 Русский brezhart 2022-03-09 21:17:31 4 Мелкая правка: 'ответ для n, c\n\n- Пуст' -> 'ответ для $n$, $c$\n\n- Пуст'
en3 Английский brezhart 2022-03-09 21:17:02 10
ru3 Русский brezhart 2022-03-09 21:16:28 6 (опубликовано)
en2 Английский brezhart 2022-03-09 21:06:30 235 Tiny change: 'determine. I attache' -> 'determine.</br></br> I attache' (published)
ru2 Русский brezhart 2022-03-09 21:02:01 1398 Мелкая правка: 'ность.\n\n<spoil' -> 'ность.\n\n\n<spoil'
en1 Английский brezhart 2022-03-09 20:50:05 1588 Initial revision for English translation (saved to drafts)
ru1 Русский brezhart 2022-03-09 20:49:17 1588 Первая редакция (сохранено в черновиках)