almost 4 years ago

果然gty一考试就要被坑死……

快坑了四个小时了

1、注意kmp的写法【尤其是j=i以及判断是否相等,不可以漏】

2、注意连边的时候顺移一位

3、!!!!注意既然不可以到m都匹配,所以从m出发以及到m的都不可以走

故在矩乘的时候是<m【被坑死了……】

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxm 22
using namespace std;
struct matrix
{
    int a[30][30];int x,y;
    void dowith(int m,int n){memset(a,0,sizeof(a));x=m;y=n;}
}map;
int n,m,Mod;
char st[maxm]={0};int next[maxm]={0};
matrix operator *(matrix p,matrix q)
{
    matrix s;s.dowith(p.x,q.y);
    for (int i=0;i<s.x;i++)
      for (int j=0;j<s.y;j++)
        for (int k=0;k<p.y;k++)
          s.a[i][j]=(s.a[i][j]+(p.a[i][k]*q.a[k][j])%Mod)%Mod;
     return s;
}
void prepare()
{
    int i,j,k,l=strlen(st);
    next[0]=-1;j=-1;
    for (i=1;i<l;i++)
      {
        while (j!=-1&&st[j+1]!=st[i]) j=next[j];
        if (st[j+1]==st[i]) j++;
        next[i]=j;
      }
}
matrix ksm(matrix map,int y)
{
    matrix result;result.dowith(map.x,map.y);
    for (int i=0;i<=max(map.x,map.y);i++)
       result.a[i][i]=1;
    for (;y>0;y>>=1)
    {
        if (y&1) result=result*map;
        map=map*map;
    }
    return result;
}
int main()
{
    int i,j,k,l,s,t;
    long long result=0;
    scanf("%d%d%d",&n,&m,&Mod);
    scanf("%s",st);
    prepare();
    map.dowith(m,m);
    for (i=0;i<m;i++)
    for (char ch='0';ch<='9';ch++)
    {
        j=i;
        while (j!=-1&&st[j+1]!=ch) j=next[j];
        if (st[j+1]==ch)map.a[j+2][i+1]=(map.a[j+2][i+1]+1)%Mod;
         else map.a[0][i+1]=(map.a[0][i+1]+1)%Mod;
    }
    map.a[0][0]=9;map.a[1][0]=1;
    map=ksm(map,n);
    for (i=0;i<m;i++)
      result=(result+map.a[i][0])%Mod;
    printf("%d\n",(int)result);
}
← 【bzoj1854】【匈牙利】游戏 【bzoj3203】【凸包】【三分】【dp】保护出题人 →
 
comments powered by Disqus