BZOJ 1009([HNOI2008]GT考试-KMP+矩阵加速Dp) (二)

2014-11-24 00:59:37 · 作者: · 浏览: 7
a*a;
b>>=1;
}
return c;
}
int a[MAXM]={0},ans[MAXM]={0};
int main()
{
//freopen("bzoj1009.in","r",stdin);
scanf("%d%d%d%s",&n,&m,&F,p+1);
kmp();
//For(i,m) cout< // a0 0..m-1
For(j,m) //0->m-1
{
//f[i][j]->f[i+1][k]
//-> f[j]->f[k]
//-> a0[k][j]
Rep(num,10)
{
if (num==p[j]-48) //j+1
{
if (j }
else
{
int t=next[j-1];
while (t&&p[t+1]-48!=num) t=next[t];
if (p[t+1]-48==num) t++;
a0(t+1,j)++;
}
}
}
//a0.print();cout< a0=pow(a0,n-1);
//a0.print();
a[1]=9,a[2]=1;
long long ans=0;
For(i,m) ans=(ans+a0(i,1)*9+a0(i,2))%F;
cout< return 0;
}