Luogu4451 [国家集训队]整数的lqp拆分


Description

\[ \begin{aligned} &F_0=0,F_1=1,F_n=F_{n-1}+F{n-2} \\ &\sum\prod_{i=1}^mF_{a_i}\models 1e9+7 \\ &m>0 \\ &a_1,a_2,a_3...a_m>0 \\ &\sum_{i=1}^ma_i=n \end{aligned} \]

Solution

因为对数字的分割是无序的,所以我们先找一个方式能枚举数字的分割。我们求出对 \(a_i=1....n\) 求出贡献再相加即可。

\(S_n\) 为所求答案,G为S_n的生成函数。容易得到递推式 \[ \begin{aligned} S_n=\sum_{i=1}^{n}F_iS_{n-i} \end{aligned} \] 即枚举 \(a_1\) 然后提取公因子。

这是一个卷积的式子,所以又可以得到 \[ \begin{aligned} &S=S*F+1 \\ &S=\frac{1}{1-F} \\ &=\frac{1}{1-\frac{x}{1-x-x^2}} \\ &=\frac{1-x-x^2}{1-2x-x^2} \end{aligned} \]

然后就能得到递推式

\[ S_0=1,S_1=1,S_2=2,S_n=2S_{n-1}+S_{n-2}(n\ge3) \]

然后再求解一下解析式,得到

\[ S_{n}=\frac{\sqrt{2}-1}{2\sqrt{2}}(-\sqrt{2}+1)^{n-1}+\frac{\sqrt{2}+1}{2\sqrt{2}}(\sqrt{2}+1)^{n-1}; \] 注意到 \(\sqrt{2}\) 存在二次剩余。所以可以快速幂求解。


文章作者: ffacs
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ffacs !
  目录