显然需要将这一线性递推关系写成矩阵形式
$$\begin{bmatrix}g_{2000}\\ g_{1999}\\ g_{1998}\\ \vdots\\ g_2\\ g_1\end{bmatrix}=\begin{bmatrix}
0 & 0 & \cdots & 0 &1 & 1\\
1 & 0 & \cdots & 0 & 0 & 0\\
0 & 1 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & \cdots & 1 & 0 & 0\\
0 & 0 & \cdots & 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix} g_{1999}\\ g_{1998}\\ g_{1997}\\ \vdots\\ g_1 \\ g_0 \end{bmatrix},$$
再用矩阵快速幂作计算。不过一般而言，矩阵乘法的复杂度是$O(n^3)$，本题中的矩阵为2000阶，仅使用快速幂还不足以计算出结果。
记等式右侧的矩阵为A，注意到$A^{2000}=I+A$（I是单位阵），因此A的任意幂$A^m$都可以表示为$I,A,\ldots, A^{1999}$的线性组合，从将矩阵乘法转化为多项式乘法。
此时再结合快速幂即可得结果$12747994$。
注：本题计算量很大， 也很难估计和打印进度，需要耐心等待。
size=2000
N=10**18
m=20092010
p=[0,1]+[0]*(size-2)
f=[1,1]+[0]*(size-2)
x=[1]+[0]*(size-1)
def cal(a,b):
c=[0]*(size*2)
for i in range(size):
for j in range(size):
c[i+j]=(c[i+j]+a[i]*b[j])%m
for i in range(size*2-1, size-1,-1):
for j in range(size):
c[i+j-size]=(c[i+j-size]+c[i]*f[j])%m
for i in range(size):
b[i]=c[i]
while N:
if N%2>0:
cal(p,x)
cal(p,p)
N>>=1
print sum(x)%m
|
