注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[HNOI2008]GT考试  

2014-04-20 18:14:21|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@ [HNOI2008]GT考试
Kmp+DP+矩阵乘法
dp:f[i][j]
完全匹配的时候不转移

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 30+1;
const int _MAX = 1000000000;
int n,m,K;
int data[N],fa[N];
inline void ref(int &x,int a){
x+=a;
while(x>K) x-=K;
}
struct matrix{
int n,m,a[N][N];
void set(const int &nn,const int &mm){
n=nn;m=mm;
memset(a,0,sizeof(a));
}
void print(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d",a[i][j]);
printf("\n");
}
}
}z,dp;
matrix inline operator * (matrix &a,matrix &b){
matrix c;
if(a.m!=b.n)
cerr<<"ERROR!!"<<endl;
c.set(a.n,b.m);
int i,j,k;
for(i=1;i<=a.n;i++)
for(j=1;j<=b.m;j++)
for(k=1;k<=a.m;k++)
ref(c.a[i][j],(a.a[i][k]*b.a[k][j])%K);
return c;
}
int pow(long long a,int k){
int re=a;k-=1;
for(;k;k>>=1,a*=a)
if(k&1)
re*=a;
return re;
}
inline matrix pow(matrix a,int k){
matrix b=a;k-=1;
for(;k;k>>=1,a=a*a)
if(k&1)
b=b*a;
return b;
}
int main(){
int i,j,k,t;
char cc;
//printf("%d ",pow(2LL,10);
//freopen("input.txt","r",stdin);
scanf("%d%d%d ",&n,&m,&K);
for(i=0;i<m;i++){
cc=getchar();
data[i]=cc-'0';
}
j=0;fa[0]=0;
for(i=1;i<m;i++){
while(j&&data[j]!=data[i]) j=fa[j];
if(data[j]==data[i])j++;
fa[i+1]=j;
}
z.set(m,1);z.a[1][1]=1;
dp.set(m,m);
for(j=0;j<m;j++)
for(k=0;k<10;k++){
t=j;
while(t&&data[t]!=k) t = fa[t];
if(data[t]==k) ++t;
if(t!=m) ref(dp.a[t+1][j+1],1);
}
//dp.print();
dp=pow(dp,n);
z=dp*z;
int ans=0;
for(i=1;i<=m;i++)
ref(ans,z.a[i][1]);
printf("%d\n",ans);
return 0;
}

[HNOI2008]GT考试 - 时光机 - 时光机TimeMachine
 
  评论这张
 
阅读(12)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017