记录编号 |
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);
}