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 (Lets coefficient of $$$x^i$$$ be $$$P_{c_{i}}$$$ ) $$$P_{c_{i}} = \frac{F(c,i)}{(\lfloor{\log_2{c}}\rfloor + i)!}$$$ where $$${F(c,i)}$$$ is some weird function I cannot determine.
I attached calculated coefficients and code for calculating them, hope someone will see a pattern there.
If someone have any information about it, please provide!
link to atcoder problem and my solution which uses the fact about polynomial of degree $$$\lfloor{\log_2{c}}\rfloor$$$
