bzoj1009GT考试

题目链接

没啥好说的，矩阵优化+$kmp$字符串匹配

上代码：

/**************************************************************

    Problem: 1009

    User: zhangheran

    Language: C++

    Result: Accepted

    Time:116 ms

    Memory:1300 kb

****************************************************************/

#include<iostream>

#include<cstdio>

//#include"suqingnian.h"

#include<algorithm>

#include<cstring>

using namespace std;

int next[];

int n,m;

int mod;

char a[];

long long ans;

void nxt()

{

    for(int i=;i<=m;i++)

    {

        int t=next[i-];

        while(t&&a[i]!=a[t+]) t=next[t];

        t+=(a[i]==a[t+]),next[i]=t;

     }

     return ;

}

struct Martix{

    long long num[][];

    friend Martix operator *(const Martix &a,const Martix &b)

    {

        Martix c;

        memset(c.num,,sizeof(c.num));

        for(int k=;k<m;k++)

          for(int i=;i<m;i++)

            for(int j=;j<m;j++)

              c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j]%mod)%mod;

        return c;

    }

    void hint(){memset(num,,sizeof(num));for(int i=;i<m;i++) num[i][i]=;}

    void clear(){memset(num,,sizeof(num));}

}p;

void kmp()

{

    nxt();

    for(int j=;j<=;j++)

      for(int k=;k<m;k++){

        int t=k;

        while(t&&a[t+]!=j+'') t=next[t];

        if(a[t+]==j+'') t++;

        p.num[k][t]++;

      }

}

Martix

    _pow(Martix _a,int _b)

    {

        Martix _res;_res.hint();

        for(;_b;_b >>= , _a= _a * _a )

          if(_b & ) _res = _res * _a ;

        return _res ;

    }

int main()

{

    scanf("%d%d%d",&n,&m,&mod);

    scanf("%s",a+);

    kmp();

    p=_pow(p,n);

//  for(int i=0;i<m;i++,puts(""))

//    for(int j=0;j<m;j++)

//      printf("%lld ",p.num[i][j]);

    for(int i=;i<m;i++) ans=(ans+p.num[][i])%mod;

    printf("%lld",ans%mod);

    return ;

}