61.187.179.132:8080/JudgeOnline/showproblem
额。。水题直接上矩阵乘法。。
由于m比较小实际上没必要用KMP算法算出原始矩阵的，不过我乘机学习了一下KMP算法囧。。
还有就是我昨天一直在调我那个QTREE的程序。。到现在都没有调好。。我真是太菜了555.
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxm=20;
int n,m,mod,A[maxm],next[maxm+1];
struct Mat
{
int M[maxm][maxm];
Mat(){memset(M,0,sizeof(M));}
void operator=(const Mat&o)
{memcpy(M,o.M,sizeof(M));}
int& operator()(int i,int j){return M[i][j];}
Mat operator*(Mat&o)
{
Mat T;
rep(i,m)rep(j,m)rep(k,m)T(i,j)+=M[i][k]*o(k,j),T(i,j)%=mod;
return T;
}
}orig;
Mat Power(int n)
{
if(n==1) return orig;
Mat tmp=Power(n/2);
tmp=tmp*tmp;
if(n&1) tmp=tmp*orig;
return tmp;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m>>mod;char x;
rep(i,m) cin>>x,A[i+1]=x-‘0’;
next[1]=0;int t=0;
for(int i=2;i<=m;i++)
{
while(t>0&&A[t+1]!=A[i]) t=next[t];
if(A[t+1]==A[i])++t;
next[i]=t;
}
for(int i=0;i<m;++i)
{
rep(j,10)
{
int t=i;
while(t>0&&A[t+1]!=j)t=next[t];
if(A[t+1]==j)++t;
orig(t,i)++;
}
}
Mat ans=Power(n);int Ans=0;
rep(i,m) Ans+=ans(i,0),Ans%=mod;
cout<<Ans<<endl;
}