dp题但n巨大一般怎么做？

发布时间：

2024-10-08 03:25

阅读量：

数列1,2,3,5,7,10,13即F(n)=F(n-1)+F(floor(n/2))是否有通项公式？

这里得到了 $f(n)$ 的生成函数为 $\frac{1}{2}\Pi_{k=0}^\infty \left(1+x^{2^k}\right)^{k+2}-\frac{1}{2}$ 。那么只需要算 $\Pi_{k=0}^\infty \left(1+x^{2^k}\right)^{k+2}$ 中 $n$ 次项的系数。记 $m=\lfloor \log_2 n\rfloor +1$ ，则只需考虑乘积的前 $m$ 项。现在从第 $m$ 项开始往回乘。乘第 $k$ 项时，注意到前 $k-1$ 项的乘积的最高次项次数是 $O(k\cdot 2^k)$ 的，而第 $k$ 项到第 $m$ 项乘积是关于 $x^{2^{k-1}}$ 的多项式，因此只需计算第 $k$ 项到第 $m$ 项乘积中的 $O(k)$ 项，剩余项的次数都太小或太大，不可能影响最终 $x^n$ 的系数。这样乘第 $k$ 项时只需进行 $O(k^2)$ 次运算，总复杂度为 $O(m^3)$ ，这里 $m\le 60$ ，能过。

上一篇：以前进的脚步为题目的作文怎么写？

下一篇： 51CTO的PMP课程怎么样?

END