综合 [国家集训队]整数的lqp拆分 题解
$$\huge \rm [国家集训队]整数的lqp拆分~题解$$
$\quad$首先有 $Fibonacci$ 数列的生成函数 ：
$$F(x)=\sum_{i\geqslant1}fib_i\cdot x^i=\frac{x}{1-x-x^2}$$
$\quad$记 $g$ 为答案数列，有 ：
$$g_n=\sum_{m>0,\sum_{i=1}^ma_i=n}\prod_{i=1}^mfib_{a_i}$$
$\quad$若当前已经有 $\sum_{j=1}^{m-1}a_j=i$，那么可以给所有方案加入一个 $a_m=n-i$，使得 $sum_{j=1}^m=n$，且贡献为 $fib_{n-i}$.
$\quad$故得到 $g$ 的递推式 ：
$$g_n=\sum_{i=0}^{n-1}g_i\cdot fib_{n-i}$$
$\quad$特别的，定义 $g_0=1$，于是我们得到了答案的生成函数 ：
$$\begin{aligned}G(x)&=\sum_{i\geqslant 0}g_i\cdot x^i\\&=\sum_{i\geqslant 0}\left(\sum_{j=0}^{i-1}g_i\cdot fib_{n-i}+[i=0]\right)x^i\\&=1+\sum_{i\geqslant 1}\left(\sum_{j=0}^{i-1}g_i\cdot fib_{n-i}\right)x^i\end{aligned}$$
$\quad$观察到由递推式得到的 $g$ 的生成函数是 $F$ 和 $G$ 的卷积形式，即 ：
$$\sum_{i\geqslant 1}\left(\sum_{j=0}^{i-1}g_i\cdot fib_{n-i}\right)x^i=F(x)\times G(x)$$
$$\therefore G(x)=1+G(x)\times F(x)$$
$$\therefore G(x)=\frac{1}{1-F(x)}=\frac{1-x-x^2}{1-2x-x^2}=1+\frac{x}{1-2x-x^2}$$
$\quad$发现式子中的 $1$ 是为了计算方便强行定义的，于是直接将其去掉，$g$ 的真正生成函数为 ：
$$G(x)=\sum_{i\geqslant 1}g_i\cdot x^i=\frac{x}{1-2x-x^2}$$
$\quad$根据部分分式定理，使用待定系数法将其展开 ：
$$\begin{aligned}\frac{x}{1-2x-x^2}&=\frac{A}{1-ax}+\frac{B}{1-bx}\\&=\frac{(A+B)+(aB-bA)x}{1-(a+b)x+abx^2}\end{aligned}$$
$\quad$对比系数得到 ：
$$\frac{x}{1-2x-x^2}=\frac{\sqrt{2}}{4}\left(\frac{1}{1-(1+\sqrt{2})x}-\frac{1}{1-(1-\sqrt{2})x}\right)$$
$\quad$故可得 $G(x)$ 的形式幂级数形式 ：
$$\begin{aligned}G(x)&=\frac{x}{1-2x-x^2}\\&=\frac{\sqrt{2}}{4}\left(\frac{1}{1-(1+\sqrt{2})x}-\frac{1}{1-(1-\sqrt{2})x}\right)\\ &=\frac{\sqrt{2}}{4}\left(\sum_{i\geqslant 0}(1+\sqrt{2})^i\cdot x^i-\sum_{i\geqslant 0}(1-\sqrt{2})^i\cdot x^i\right)\\&=\frac{\sqrt{2}}{4}\sum_{i\geqslant 0}\left[(1+\sqrt{2})^i-(1-\sqrt{2})^i\right]x^i\end{aligned}$$
$$\therefore g_n=\frac{\sqrt{2}}{4}\left[(1+\sqrt{2})^n-(1-\sqrt{2})^n\right]$$
$\quad$现在考虑如何计算 $g_n$，观察到其中有无理数 $\sqrt{2}$，于是要先求出 $\sqrt{2}$ 在模 $10^9+7$ 意义下的值，即以下同余方程的解 ：
$$x^2\equiv 2\pmod{10^9+7}$$
$\quad$考虑一个更一般的问题 ：求 $\sqrt{n}$ 在模 $p$ 意义下的值。其等价于解下面的同余方程 ：
$$x^2\equiv n\pmod p$$
$\quad$定义 $n$ 是模 $p$ 意义下的二次剩余，当且仅当同余方程 $x^2\equiv n\pmod p$ 有解，也就是存在一个整数在模 $p$ 意义下等价于 $\sqrt{n}$.
$\quad$那么对于一个模 $p$ 意义下的二次剩余 $n$，方程 $x^2\equiv n\pmod p$ 有多少个解呢 $？$
$\quad$假设有多个解，取其中任意两个不同的 $x_1,x_2$，有 ：
$$x_1^2\equiv x_2^2\Longrightarrow (x_1+x_2)(x_1-x_2)\equiv 0\pmod p$$
$\quad$由于 $x_1\not= x_2$，所以 $x_1+x_2\equiv 0\pmod p$. 换而言之，对于任意一个二次剩余 $n$，存在两个解 $x_1,x_2$ 使得方程 $x^2\equiv n\pmod p$ 成立，且它们互为相反数。另外，因为 $p$ 是一个奇质数，所以 $x_1$ 和 $x_2$ 在模 $p$ 意义下不相等。
$\quad$由于任意一个二次剩余都对应一对互为相反数的解，且易知任意一对相反数也对应一个二次剩余，故二次剩余的个数恰为 $\frac{p-1}{2}$.
$\quad$那如何快速判断一个数 $n$ 是否为模 $p$ 意义下的二次剩余呢 $?$
$\quad$由费马小定理可知 ：
$$n^{p-1}\equiv 1\Longrightarrow \left(n^{\frac{p-1}{2}}\right)^2-1\equiv0\pmod p$$
$\quad$所以 $n^{\frac{p-1}{2}}$ 在模 $p$ 意义下可能有两个值，即 $1$ 或 $-1$.
$\quad$如果 $n$ 是二次剩余，那么有 ：
$$n^{\frac{p-1}{2}}\equiv (x^2)^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1\pmod p$$
$\quad$于是 $n$ 为模 $p$ 意义下的二次剩余当且仅当 $n^{\frac{p-1}{2}}\equiv 1\pmod p$.
$\quad$有了以上两个引理，寻找方程 $x^2\equiv n\pmod p$ 的解可以使用 $\rm Cipolla$ 算法。
$\quad$首先找到一个 $a$，满足 $a^2-n$ 是非二次剩余，我们可以随机找，由于非二次剩余的数量占总数的 $\frac{1}{2}$，所以期望随机两次可以找到。
$\quad$定义 $i^2\equiv a^2-n\pmod p$，但 $a^2-n$ 不是二次剩余，所以在整数域内找不到一个 $i$ 可以满足这个式子，于是考虑扩域，接下来所有数都在类复数域内讨论，每个数都可以被表示为 $a+bi$ 的形式，其中 $a$ 和 $b$ 是模 $p$ 意义下的值，类似于复数的实部和虚部。
$\quad$有 $(a+i)^{p+1}\equiv n\pmod p$，考虑证明。
$\quad$引理 $1$ ：$(a+b)^p\equiv a^p+b^p\pmod p$
$Proof$.
$$(a+b)^p\equiv \sum_{i=0}^p \dbinom{p}{i}a^i\cdot b^{p-i}\equiv a^p+b^p+\sum_{i=1}^{p-1}\frac{p!}{i!(n-i)!}a^i\cdot b^{n-i}\equiv a^p+b^p\pmod p$$
$\quad$引理 $2$ ：$i^p\equiv -i\pmod p$
$Proof$.
$$i^p\equiv i(i^2)^{\frac{p-1}{2}}\equiv i(a^2-n)^{\frac{p-1}{2}}\equiv -i\pmod p$$
$$\begin{aligned} (a+i)^{p+1}&=(a+i)^p(a+i)\\ &\equiv (a^p+b^p)(a+i)\\ &\equiv (a-i)(a+i)\\&\equiv a^2-i^2\\&\equiv n\pmod p\end{aligned}$$
$\quad$所以 $x_0=(a+i)^{\frac{p+1}{2}}$ 是方程 $x^2\equiv n\pmod p$ 的一个解。
$\quad$言归正传，用这种方法可以求出 $\sqrt{2}$ 在模 $p$ 意义下的值为 $59713600$ 或 $940286407$.
$\quad$另一方面，由于 $n$ 的值很大，根据费马小定理，可以直接将其对 $p-1$ 取模。
$\quad$综上，我们可以在 $\Theta(\log p)$ 的时间复杂度下求出答案 ：
$$g_n=14928400\times \left(59713601^{n~mod~(p-1)}-940286408^{n~mod~(p-1)}\right)$$