Bubble Cup 9

Bubble Cup 9

跟着akc做题;还有一个blog

CF717A Festival Organization

请先思考后再展开

$$
\begin{aligned}
ans&=solve(r+2)-solve(l+1) \\
solve(n)&=\sum_{i=0}^n C_{fib(i)}^k=\frac{1}{k!} \sum_{i=0}^n fib(i)^{\underline k}\\
&=\frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} S_2(k,j)[ \sum_{i=0}^n fib^j(i) ] \\
pp&=\frac{1+\sqrt{5}}{2},fib(i)=\frac{pp^i+(-1)^{i+1}pp^{-i}}{\sqrt{5}} \\
\sum_{i=0}^n fib^j(i)&=(1/\sqrt{5})^j \sum_{t=0}^j C_j^t \sum_{i=0}^n (-1)^{(i+1)t} (pp^{(j-2t)})^i \\
&=(1/\sqrt{5})^j \sum_{t=0}^j C_j^t (-1)^t \sum_{i=0}^n (A=pp^{j-2t}(-1)^t)^i \\
时间复杂度为 & O(k^2log_R),类似复数去存就好了,等比数列求和用分治即可
\end{aligned}
$$

B

请先思考后再展开

###

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/32e3.html
转载请注明出处,谢谢!