记录编号	414604	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]GT考试	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2017-06-14 17:08:37	内存使用	0.32 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,mod;
char s[25];
int kp[25];
inline void get_kp(){
	kp[0]=0;
	kp[1]=0;
	int k(0);
	for(int i=2;i<=m;i++){
		while(k&&s[k]!=s[i-1])
			k=kp[k];
		if(s[k]==s[i-1])
			k++;
		kp[i]=k;
	}
}
struct node{
	int data[25][25];
	node(){
		memset(data,0,sizeof(data));
	}
	node operator*(node &a){
		node tmp;
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++){
				tmp.data[i][j]=0;
				for(int k=0;k<m;k++){
					tmp.data[i][j]+=(data[i][k]*a.data[k][j]);
					tmp.data[i][j]%=mod;
				}
			}
		return tmp;
	}
	node operator*=(node &a){
		*this=*this*a;
		return *this;
	}
}a,sing;
ostream& operator<<(ostream &out,node &a){
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++)
			out<<a.data[i][j]<<' ';
		out<<endl;
	}
	return out;
}
int main(){
	freopen("bzoj_1009.in","r",stdin);
	freopen("bzoj_1009.out","w",stdout);
	scanf("%d%d%d%s",&n,&m,&mod,s);
	get_kp();
	for(int i=0;i<m;i++)
		for(int j=0;j<=9;j++){
			int k(i);
			while(k&&(j+'0')!=s[k])
				k=kp[k];
			if(j+'0'==s[k])
				k++;
			if(k!=m){
				a.data[i][k]++;
				a.data[i][k]%=mod;//cout<<'*';
			}
		}//cout<<a<<endl;
	/*for(int i=0;i<m;i++){
		for(int j=0;j<m;j++)
			cout<<a[i][j]<<' ';
		cout<<'\n';
	}*/
	for(int i=0;i<m;i++)
		sing.data[i][i]=1;
	int tmp(n);
	while(tmp){
		if(tmp&1)
			sing*=a;
		a*=a;
		//cout<<tmp<<endl;
		//cout<<a<<endl<<sing<<endl;
		tmp>>=1;
	}
	int ans(0);
	for(int i=0;i<m;i++){
		ans=(ans+sing.data[0][i])%mod;
		//cout<<ans<<endl;
	}
	cout<<ans;
	//while(1);
}