Searching for a pattern

Revision en1, by brezhart, 2022-03-09 20:50:05

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}$$$ (Lets coefficient of $$$x^i$$$ be $$$P_{c, i}$$$ ) Seems like $$$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.

coefficients
code for calculating coefficients

If someone have any information about it, please provide!

link to atcoder problem and my solution which uses the fact about $$$\lfloor{\log_2{c}}\rfloor$$$ polynomial

!I know there is O(ClogC) or even O(C) solutions, im just exploring this problem a little more!

History

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