题目描述
给定 $l,r,k$，其中 $1 \le k \le 501, 1 \le l \le r \le 10^{18}$
令 $f_n$ 为用 $1 \times 2$ 的骨牌拼 $2 \times n$ 方格的方案数，$g_n$ 为用 $1 \times 2$ 的骨牌拼 $3 \times n$ 方格的方案数
求 $\sum_{i=l}^{r}{f_i \choose k}$ 和 $\sum_{i=l}^{r}{g_i \choose k}$，输出模 $998244353$
题解
首先有：
$$
{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
$$
和第一问的做法一样
希望以后不会遇到这种强行多合一的出题人……
