把m次来回放看作是有2m只青蛙同时在一条长为n的格子上跳跃。
一次最多跳三格，所以状态可以表示为一个长度为5的向量，分别表示当前格，跳一格、跳两格、跳三格的青蛙数变化、以及是否遗漏过格子。由于青蛙总数恒定，前四项实际上可以缩减为三项。
将状态之间的转移表示为矩阵，再用矩阵快速幂计算即得结果$898082747$。
注：因用到math.comb方法， 以下代码为Python 3，且代码中打印了进度信息。
import math
mod=1000000000
b=20
s=[(i,j,b-i-j,0) for i in range(b,-1,-1) for j in range(b-i,-1,-1) if i or j]+[(i,j,b-i-j,1) for i in range(b,0,-1) for j in range(b-i,-1,-1)]
n=len(s)
d={j:i for i,j in enumerate(s)}
A=[[0]*n for i in range(n)]
for y,x in enumerate(s):
for i in range(x[0]+1):
for j in range(x[1]+1):
if ((u:=x[0]-i+x[1]-j+x[2])>0 or x[3]>0) and (t:=(u,i,j,1 if x[3]*u>0 else 0)) in d:
A[d[t]][y]=(A[d[t]][y]+math.comb(x[0],i)*math.comb(x[1],j))%mod
x=[0]*n
x[d[(b,0,0,1)]]=1
k=1000000000000-2
while k>0:
if k%2==1:
x=[sum(A[i][j]*x[j] for j in range(n))%mod for i in range(n)]
A=[[sum(A[i][k]*A[k][j] for k in range(n))%mod for j in range(n)] for i in range(n)]
k//=2
print(k,"current sum:",sum(x)%mod)
print(sum(x)%mod)
|
