设不超过i位的数中模23余j且数位和为k的数共有$v_i(j,k)$个，那么有初值$v_1(i,i)=1$ ($0\le i\le 9$) 以及递推公式
$$v_{i+1}(j,k)=\sum_{d=0}^{\min(9,k)}\sum_{j'}v_i(j',k-d),$$
其中j'取遍满足$10j'+d\bmod 23=j$的数。
需要计算的n非常巨大，因此把这一递推公式改写成矩阵形式并用矩阵快速幂计算即可得结果789184709。
N=pow(11,12)
target=23
v=[[0]*(target+1) for i in range(target+1)]
x=[[0]*(target+1) for i in range(target+1)]
def cal(a,b,c):
y=[[0]*(target+1) for i in range(target+1)]
for i in range(target):
for j in range(target):
for u in range(target+1):
for v in range(target+1-u):
y[(c*i+j)%target][u+v]+=a[i][u]*b[j][v]
y[(c*i+j)%target][u+v]%=1000000000
return y
for i in range(10):
v[i][i]=x[i][i]=1
p=10
n=N-1
i=0
while n:
if n%2==1:
x=cal(x,v,p)
v=cal(v,v,p)
p=pow(p,2,target)
n>>=1
i+=1
print x[0][target]
|
