令$f _{i,j,k}$表示$i$位，模$p$余$j$，数字和恰好为$k$的数的个数，那么可以写出递推式
可以发现这很像一个卷积的形式，但是$j$这一维很难用多项式来优化. 这个时候可以考虑倍增，列出更一般的递推式
这样让$F _i(x,y)=\sum f _{i,j,k}x^jy^k$就可以用倍增+NTT来加速了，（$x$直接暴力卷积，$y$用NTT优化）.
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
using namespace std;
ele n,p,m,a[maxp][maxn],b[maxp][maxn];
inline ele pw(ele a,ele x){
ele ans=1,tmp=a%MOD;
for (; x; x>>=1,tmp=(ll)tmp*tmp%MOD)
if (x&1) ans=(ll)ans*tmp%MOD;
return ans;
}
inline void NTT(ele K,ele n,ele *y){
static ele f[maxn];
f[0]=0;
for (int i=1; i<n; ++i){
f[i]=f[i>>1]>>1;
if (i&1) f[i]+=n>>1;
if (i<f[i]) swap(y[i],y[f[i]]);
}
for (int p=1; p<n; p<<=1){
ele o=pw(g,(MOD-1)/p/2);
o=~K?o:pw(o,MOD-2);
for (int i=0; i<n; i+=(p<<1)){
ele o1=1;
for (int j=i; j<i+p; ++j,o1=(ll)o1*o%MOD){
ele u=y[j],v=(ll)y[j+p]*o1%MOD;
y[j]=(u+v)%MOD;
y[j+p]=(u-v+MOD)%MOD;
}
}
}
if (!~K){
ele invn=pw(n,MOD-2);
for (int i=0; i<n; ++i) y[i]=(ll)y[i]*invn%MOD;
}
}
inline void mul(ele a[maxp][maxn],ele b[maxp][maxn],ele k){
static ele c[maxp][maxn],d[maxp][maxn],e[maxp][maxn];
memset(c,0,sizeof(c));
ele tmp=1;
while (tmp<m+m-1) tmp<<=1;
memset(d,0,sizeof(d)); memcpy(e,b,sizeof(e));
for (int i=0; i<p; ++i){
ele j=i*k%p;
for (int r=0; r<m; ++r) (d[j][r]+=a[i][r])%=MOD;
}
for (int i=0; i<p; ++i) NTT(1,tmp,d[i]),NTT(1,tmp,e[i]);
for (int i=0; i<p; ++i)
for (int j=0; j<p; ++j){
ele k=(i+j)%p;
for (int r=0; r<tmp; ++r)
(c[k][r]+=(ll)d[i][r]*e[j][r]%MOD)%=MOD;
}
memcpy(a,c,sizeof(c));
for (int i=0; i<p; ++i) NTT(-1,tmp,a[i]);
for (int i=0; i<p; ++i)
for (int j=m; j<tmp; ++j) a[i][j]=0;
}
int main(){
scanf("%d%d%d",&n,&p,&m); ++m;
memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
a[0][0]=1;
for (int i=0; i<10 && i<m; ++i) b[i%p][i]+=1;
ele k=10;
for (; n; n>>=1,mul(b,b,k),k=k*k%p)
if (n&1) mul(a,b,k);
ele cnt=0;
for (int i=0; i<m; ++i) (cnt+=a[0][i])%=MOD,printf(i?" %d":"%d",cnt);
puts("");
return 0;
}