显然有$F_0(x)=0, F_1(x)=x$以及
$$F_n(x)=xF_{n-1}(x)+x^2F_{n-2}(x)+x,$$
将其写作矩阵形式
$$
\begin{pmatrix}
F_{n}(x)\\
F_{n-1}(x)\\
x
\end{pmatrix}
=
\begin{pmatrix}
x & x^2 & 1\\
1 & 0 & 0\\
0 & 0 & 1
\end{pmatrix}\begin{pmatrix}
F_{n-1}(x)\\
F_{n-2}(x)\\
x
\end{pmatrix}$$
对每个x，矩阵快速幂求解$F_{10^{15}}(x)$再汇总即得结果$252541322550$。
N=10**15
mod=1307674368000
mul=lambda A,B:[[sum(A[i][k]*B[k][j] for k in range(len(B)))%mod for j in range(len(B[0]))] for i in range(len(A))]
def mqp(A,e):
if e==1:return A
B=mqp(A,e//2)
return mul(B,B) if e%2==0 else mul(mul(B,B),A)
res=0
for x in range(101):
v=[[x],[0],[x]]
M=[[x, x*x, 1],[1,0,0],[0,0,1]]
res=(res+mul(mqp(M,N-1),v)[0][0])%mod
print res
|
