题目链接

题目描述

给定 $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
$$

和第一问的做法一样


希望以后不会遇到这种强行多合一的出题人……