题解：P4451 [国家集训队] 整数的lqp拆分

· · 题解

Solution

首先考虑答案的生成函数。设 F(x)=\dfrac{x}{1-x-x^2} 为斐波那契数列的生成函数。钦定选多少个数，则答案的生成函数为：

G(x)=\sum_{i\ge 0}F(x)^i=\frac{1}{1-F(x)}

于是

G(x)=\frac{1-x-x^2}{1-2x-x^2}=1+\frac{x}{1-2x-x^2}

到这里已经可以 Bostan-Mori 搞了。

接下来我们尝试求出 G(x) 的通项。

使用《具体数学》7.3 节中的方法。具体地，设 R(x)=\dfrac{P(x)}{Q(x)}。若我们可以将 R(x) 表示成形如

R(x)=T(x)+\sum_{i=1}^l\frac{a_i}{(1-\rho_ix)^{m_i+1}}

的形式，则其系数 [x^n]R(x) 可以表示为：

[x^n]R(x)=[x^n]T(x)+\sum_{i=1}^la_i{m_i+n\choose m_i}\rho_i^n

的形式。

考虑 Q(x)=\sum_{i=0}^kq_ix^i 的”反射“多项式 Q^R(x)=\sum_{i=0}^kq_{k-i}x^i，它们之间的关系我们在多项式除法中讨论过：

Q(x)=x^kQ^R(\frac{1}{x})

那么有

Q^R(x)=q_0\prod_{i=1}^k(x-\rho_i)\iff Q(x)=q_0\prod_{i=1}^k(1-\rho_ix)

于是，我们求出 Q^R(x)=0 的根，便能得到 \rho_i 的表示。对于 a_i 的处理，待定系数即可。

令 R(x)=G(x)，易得 T(x)=1,P(x)=x,Q(x)=1-2x-x^2。

运用上述方法，我们求解 Q^R(x)=x^2-2x-1=0 的根。解得

x_1=1+\sqrt 2,x_2=1-\sqrt 2

于是有 Q(x)=(1-(1+\sqrt 2)x)(1-(1-\sqrt 2)x)。设 \dfrac{P(x)}{Q(x)}=\dfrac{x}{1-2x-x^2}=\dfrac{a_1}{1-(1+\sqrt 2)x}+\dfrac{a_2}{1-(1-\sqrt 2)x}，待定系数可得：

a_1+a_2=0\\ -a_1(1-\sqrt 2)-a_2(1+\sqrt 2)=1 \end{cases}

解得

a_1=\frac{\sqrt 2}{4}\\ a_2=-\frac{\sqrt 2}{4} \end{cases}

于是我们得到了 R(x) 的表示：

R(x)=1+\frac{\frac{\sqrt 2}{4}}{1-(1+\sqrt 2)x}+\frac{\frac{\sqrt 2}{4}}{1-(1-\sqrt 2)x}

然后就有 [x^n]R(x) 的系数表示：

[x^n]R(x)=[n=0]+\frac{\sqrt 2}{4}\times(1+\sqrt 2)^n-\frac{\sqrt 2}{4}\times (1-\sqrt 2)^n

指数可以使用欧拉定理。注意到 2 在模 10^9+7 意义下存在二次剩余，所以我们没必要扩域。