首页
关于
笔记
文章
友链

Solution -「CF 392C」Yet Another Number Sequence

cirnovsky /

§ Description

Link.

求 ∑i=1nfibonaccii×ik=∑i=1n(Fi−1+fibonaccii−2)×ik\sum_{i=1}^{n}\text{fibonacci}_{i}\times i^{k}=\sum_{i=1}^{n}(F_{i-1}+\text{fibonacci}_{i-2})\times i^{k}，1≤n≤1017,1≤k≤401\le n\le10^{17},1\le k\le40。

§ Solution

简记 Fi=fibonacciiF_{i}=\text{fibonacci}_{i}。首先我们作个差：

ansn=∑i=1nFi×ik=∑i=1n(Fi−1+Fi−2)×ikansn−ansn−1=Fn×nkans_{n}=\sum_{i=1}^{n}F_{i}\times i^{k}=\sum_{i=1}^{n}(F_{i-1}+F_{i-2})\times i^{k} \\ ans_{n}-ans_{n-1}=F_{n}\times n^{k} \\

然后：

ansn=ansn−1+Fn×nk=ansn−1+Fn−1×(n−1+1)k+Fn−2×(n−2+2)k=ansn−1+(∑i=0kAi−1(i)×(ki))+(∑i=0kAi−2(i)×(ki)×2k−i)\begin{aligned} ans_{n}&=ans_{n-1}+F_{n}\times n^{k} \\ &=ans_{n-1}+F_{n-1}\times(n-1+1)^{k}+F_{n-2}\times(n-2+2)^{k} \\ &=ans_{n-1}+\left(\sum_{i=0}^{k}A_{i-1}(i)\times\binom{k}{i}\right)+\left(\sum_{i=0}^{k}A_{i-2}(i)\times\binom{k}{i}\times2^{k-i} \right) \end{aligned}

后面的 dirty work 实在不想做，口胡选手选择放弃。

Oops, something went wrong.