Im working on this problem: Given $n$ and $c$, How many sequences $A$ of length $n$ satisfy the following conditions:↵
↵
- $1\leq a_{i} \leq c$↵
- $\forall i \in {1,2,\ldots,n-1}: a_{i} | a_{i+1} $ ($a_{i+1}$ is multiple of $a_{i}$)↵
↵
#### I found really cool fact:↵
↵
- lets $ANS_{n,c}$ be the answer for $n$, $c$↵
↵
- Lets $A_{c} = ANS_{1,c},ANS_{2,c},ANS_{3,c},\ldots$↵
↵
Surprisingly, $A_{c}$ can be represented as polynomial $P_{c}$ of degree exactly $\lfloor{\log_2{c}}\rfloor$, so $P_{c}(X) = ANS_{X,c}$↵
↵
Why is even $\log_2$ came up here?↵
↵
By the way, im struggle to find pattern for coefficients of $P_{c}$. I noticed that <span style="white-space: nowrap;">(Lets coefficient of $x^i$ be $P_{c, i_{i}}$ )</span> $P_{c,i_{i}} = \frac{F(c,i)}{(\lfloor{\log_2{c}}\rfloor + i)!}$ where ${F(c,i)}$ is some weird function I cannot determine.<br><br> I attached calculated coefficients and code for calculating them, hope someone will see a pattern there.↵
↵
<spoiler summary="coefficients">[link](https://gist.github.com/brezhart/a9fb5a37139946dd8cb839ef9fd9c706)</spoiler>↵
↵
<spoiler summary="code for calculating coefficients">[link](https://gist.github.com/brezhart/a2ca9571494429805b4132445b585350)</spoiler>↵
↵
If someone have any information about it, please provide!↵
↵
[link to atcoder problem](https://atcoder.jp/contests/arc116/tasks/arc116_c) and [my solution](https://atcoder.jp/contests/arc116/submissions/29935374) which uses the fact about polynomial↵
of degree $\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}$ is multiple of $a_{i}$)↵
↵
#### I found really cool fact:↵
↵
- lets $ANS_{n,c}$ be the answer for $n$, $c$↵
↵
- Lets $A_{c} = ANS_{1,c},ANS_{2,c},ANS_{3,c},\ldots$↵
↵
Surprisingly, $A_{c}$ can be represented as polynomial $P_{c}$ of degree exactly $\lfloor{\log_2{c}}\rfloor$, so $P_{c}(X) = ANS_{X,c}$↵
↵
Why is even $\log_2$ came up here?↵
↵
By the way, im struggle to find pattern for coefficients of $P_{c}$. I noticed that <span style="white-space: nowrap;">(Lets coefficient of $x^i$ be $P_{c
↵
<spoiler summary="coefficients">[link](https://gist.github.com/brezhart/a9fb5a37139946dd8cb839ef9fd9c706)</spoiler>↵
↵
<spoiler summary="code for calculating coefficients">[link](https://gist.github.com/brezhart/a2ca9571494429805b4132445b585350)</spoiler>↵
↵
If someone have any information about it, please provide!↵
↵
[link to atcoder problem](https://atcoder.jp/contests/arc116/tasks/arc116_c) and [my solution](https://atcoder.jp/contests/arc116/submissions/29935374) which uses the fact about polynomial↵
of degree $\lfloor{\log_2{c}}\rfloor$↵
↵
