由OEIS A181688中的公式可知，$T(1)=T(2)=1$，$T(3)=4$，$T(4)=8$，对$n\ge 5$有
$$T(n)=2T(n-1)+2T(n-2)-2T(n-3)+T(n-4)$$
这一递推式也可写作
$$\begin{pmatrix}T(n) \\ T(n-1) \\ T(n-2) \\ T(n-3)\end{pmatrix}=\begin{pmatrix} 2 & 2 & -2 & 1\\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix}T(n-1) \\ T(n-2) \\ T(n-3) \\ T(n-4) \end{pmatrix}$$
从而需要计算
$$\begin{pmatrix} 2 & 2 & -2 & 1\\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}^{10^{12}-4}\begin{pmatrix}8 \\ 4 \\ 1 \\ 1 \end{pmatrix}$$
的第一个分量，使用快速幂的技巧计算即得结果$15836928$。
n=10**12-4
m=10**8
f=lambda A,B:[[sum(A[i][k]*B[k][j] for k in range(4))%m for j in range(len(B[0]))] for i in range(4)]
A=[[2,2,-2,1],[1,0,0,0],[0,1,0,0],[0,0,1,0]]
x=[[8],[4],[1],[1]]
while n:
if n%2==1:
x=f(A,x)
A=f(A,A)
n>>=1
print x[0][0]
|
