题解 P5320 【[BJOI2019]勘破神机】
nekko
2019-04-21 12:22:29
首先有：
$${f_n \choose k}=\frac{f_n^{\underline k}}{k!}$$
由于：
$$x^{\underline{n}}= \sum_{i=0}^{n} \begin{bmatrix} n \\ i \end{bmatrix}(-1)^{n-i} x^i$$
可以得出：
$$f_{n}^{\underline k}=\sum_{i=0}^{k} \begin{bmatrix}k\\i \end{bmatrix} (-1)^{k-i} f_n^i$$
则：
$$\begin{aligned} &\sum_{i=l}^{r} {f_i \choose k} \\ =&\frac{1}{k!} \sum_{i=l}^{r} f_i^{\underline k} \\ =&\frac{1}{k!}\sum_{i=l}^{r} \sum_{j=0}^{k} \begin{bmatrix}k\\j \end{bmatrix} (-1)^{k-j} f_{i}^j \\ =&\frac{1}{k!}\sum_{j=0}^{k} \begin{bmatrix}k\\j \end{bmatrix} (-1)^{k-j} \sum_{i=l}^{r} f_i^j \end{aligned}$$
---
强行二合一，那么先解决前半部分
显然有：
$$\begin{cases} f_0=1 \\ f_1=1 \\ f_{n}=f_{n-1}+f_{n-2} \end{cases}$$
对于方程 $x^2=x+1$，有根 $x=\frac{1 \pm \sqrt{5}}{2}$
即：
$$f_n=a\left( \frac{1 + \sqrt{5}}{2} \right)^n+b\left( \frac{1-\sqrt{5}}{2} \right)^n$$
由 $f_0=f_1=1$，解得：
$$\begin{cases} a=\frac{1+\frac{1}{\sqrt{5}}}{2} \\ b=\frac{1-\frac{1}{\sqrt{5}}}{2} \end{cases}$$
即：
$$f_n=\frac{1+\frac{1}{\sqrt{5}}}{2} \left( \frac{1+\sqrt{5}}{2} \right)^n + \frac{1-\frac{1}{\sqrt{5}}}{2} \left( \frac{1-\sqrt{5}}{2} \right)^n$$
也就是：
$$f_n=\frac{5+\sqrt{5}}{10} \left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{5-\sqrt{5}}{10} \left(\frac{1-\sqrt{5}}{2}\right)^n$$
考虑在 $\mathbb{Z}[\sqrt{5}]$ 上定义 $(a,b)$，相当于映射到 $\mathbb{R}$ 上的 $a\sqrt{5}+b$，定义其上的运算如下：
对于二元运算 $+$，有：
$$(a,b)+(c,d)=(a+c,b+d)$$
对于二元运算 $-$，有：
$$(a,b)-(c,d)=(a-c,b-d)$$
对于二元运算 $\times$，有：
$$(a,b) \times (c,d) = (ad+bc,5ac+bd)$$
对于一元运算 $(a,b)^{-1}$，有：
$$(a,b)^{-1}=(\frac{a}{5a^2-b^2}, -\frac{b}{5a^2-b^2})$$
即：
$$f_n=(\frac{1}{10}, \frac{1}{2}) \times (\frac{1}{2},\frac{1}{2})^n+(-\frac{1}{10}, \frac{1}{2}) \times (-\frac{1}{2},\frac{1}{2})^n$$
为了简便起见，记 $f_n=ax_0^n+bx_1^n$
那么现在只需要求：
$$\sum_{i=1}^{n} f_i^k$$
也就是：
$$\begin{aligned} &\sum_{i=1}^{n} \sum_{j=0}^{k} {k \choose j} (ax_0^i)^j (bx_1^i)^{k-j} \\ =&\sum_{j=0}^{k} {k \choose j} \sum_{i=1}^{n} a^j(x_0^j)^i b^{k-j}(x_1^{k-j})^i \\ =&\sum_{j=0}^{k} {k \choose j} a^jb^{k-j}\sum_{i=1}^{n} (x_0^jx_1^{k-j})^i \\ \end{aligned}$$
通过等比数列求和，有：
$$\sum_{i=1}^{n} (a,b)^i=\frac{(a,b)^{n+1}-(a,b)}{(a,b)-(0,1)}$$
前半部分结束了
---
对于后半部分，显然有：
$$\begin{cases} f_{2n}= f_{2n-2} + 2 \sum_i f_{2n-2i} \\ f_{2n+1}=0 \end{cases}$$
设 $h_n=f_{2n}$，则：
$$\begin{aligned} & \begin{cases} h_n=h_{n-1}+2\sum_{i}h_{n-i} \\ h_{n+1}=h_{n}+2\sum_{i}h_{n+1-i}=h_{n}+2h_{n}+2\sum_{i}h_{n-i} \\ \end{cases} \\ \Rightarrow & h_{n}-h_{n+1}=h_{n-1}-3h_{n} \\ \Rightarrow & h_{n+1}=4h_{n}-h_{n-1} \\ \Rightarrow & h_{n}=4h_{n-1}-h_{n-2} \end{aligned}$$
即：
$$\begin{cases} h_0=1 \\ h_1=3 \\ h_n=4h_{n-1}-h_{n-2} \end{cases}$$
对于方程 $x^2=4x-1$，有根 $x=2 \pm \sqrt{3}$
即：
$$h_n=ax_0^n+bx_1^n$$
解得：
$$\begin{cases} a=\frac{3+\sqrt{3}}{6} \\ b=\frac{3-\sqrt{3}}{6} \end{cases}$$
即：
$$h_n=\frac{3+\sqrt{3}}{6} (2+\sqrt{3})^n+\frac{3-\sqrt{3}}{6}(2-\sqrt{3})^n$$
不妨设 $h_n=ax_0^n+bx_1^n$
即：
$$f_n=[2|n] \left( ax_0^{\frac{n}{2}} + bx_1^{\frac{n}{2}} \right)$$
目标是要求：
$$\frac{1}{k!}\sum_{j=0}^{k} \begin{bmatrix}k\\j \end{bmatrix} (-1)^{k-j} \sum_{i=l}^{r} f_i^j$$
也就是求：
$$\sum_{i=1}^{n} f_{i}^{j}=\sum_{i=1}^{n}[2|n]f_i^j=\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} h_i^j$$
和第一问的做法一样
---
希望以后不会遇到这种强行多合一的出题人……