【BZOJ1009】GT考试（HNOI2008）-DP矩阵优化+KMP

做法：本题需要用到DP矩阵优化+KMP。
令串）。注意到这个过程和KMP算法非常相似，甚至完全一样，所以我们可以用KMP来优化这个过程。
注意到上述的方法是。
以下是本人代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,K,fail[30];
char s[30];
struct matrix {int s[25][25];} E,N,M[35];

void init()
{
    scanf("%d%d%d",&n,&m,&K);
    s[0]='#';
    scanf("%s",s+1);
}

void kmp()
{
    fail[0]=-1;
    for(int i=1;i<=m;i++)
    {
        int x=fail[i-1];
        while(x!=-1&&s[x+1]!=s[i]) x=fail[x];
        if (s[x+1]!=s[i]) fail[i]=0;
        else fail[i]=x+1;
    }
}

matrix mult(matrix A,matrix B)
{
    matrix S=N;
    for(int i=0;i<=m;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=m;k++)
                S.s[i][j]=(S.s[i][j]+A.s[i][k]*B.s[k][j])%K;
    return S;
}

matrix power(int x)
{
    matrix S=E;
    int i=0;
    while(x)
    {
        if (x&1) S=mult(S,M[i]);
        x>>=1,i++;
    }
    return S;
}

void build()
{
    for(int i=0;i<=m;i++)
        for(int j=0;j<=m;j++)
            N.s[i][j]=0;
    M[0]=E=N;
    for(int i=0;i<=m;i++) E.s[i][i]=1;
    for(int i=0;i<m;i++)
        for(int j=0;j<=9;j++)
        {
            char c=j+'0';
            int x=i;
            while(x!=-1&&s[x+1]!=c) x=fail[x];
            if (s[x+1]!=c) M[0].s[0][i]=(M[0].s[0][i]+1)%K;
            else M[0].s[x+1][i]=(M[0].s[x+1][i]+1)%K;
        }
    for(int i=1;i<=32;i++) M[i]=mult(M[i-1],M[i-1]);
}

void solve()
{
    matrix S=power(n);
    int ans=0;
    for(int i=0;i<m;i++) ans=(ans+S.s[i][0])%K;
    printf("%d",ans);
}

int main()
{
    init();
    kmp();
    build();
    solve();

    return 0;
}