BZOJ1009

传送门：BZOJ1009

KMP构造转移矩阵，矩阵加速DP。
以后题解都会简单一些。

/**************************************************************
    Problem: 1009
    User: Jerusalem
    Language: C++
    Result: Accepted
    Time:56 ms
    Memory:1492 kb
****************************************************************/

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

int mod;

struct Matrix{
    int m[25][25];
    Matrix(){
        memset(m,0,sizeof(m));
    }
    Matrix C(int a,int b,int c,int d,Matrix o){
        Matrix q;
        for(int i=0;i<a;i++)
            for(int j=0;j<b;j++)
                for(int k=0;k<d;k++){
                    q.m[i][k]+=((m[i][j]*o.m[j][k])%mod);
                    q.m[i][k]%=mod;
                }
        return q;
    }
};

char num[25];
int pre[25];
int n,m;
int f[25];
int g[25];
int ans;
Matrix E;
Matrix M;

void Make_Table()
{
    pre[1]=0;int k=0;
    for(int i=2;i<=m;i++){
        while(k&&num[k+1]!=num[i])
            k=pre[k];
        if(num[k+1]==num[i])
            k++;
        pre[i]=k;
    }
    for(int i=0;i<m;i++)
        for(int j=0;j<=9;j++){
            k=i;
            while(k&&num[k+1]!=j)
                k=pre[k];
            if(num[k+1]==j)
                M.m[i][k+1]++;
            else
                M.m[i][0]++;
        }
    for(int i=0;i<m;i++)
        E.m[i][i]=1;
}

Matrix Power(Matrix A,int b)
{
    if(b==0)
        return E;
    if(b==1)
        return A;
    Matrix mid=Power(A,b/2);
    if(b%2==0)
        return mid.C(m,m,m,m,mid);
    return ((mid.C(m,m,m,m,mid)).C(m,m,m,m,A));
}

void Solve()
{
    M=Power(M,n);
    for(int i=0;i<m;i++){
        ans+=M.m[0][i];
        ans%=mod;
    }
    printf("%d\n",ans);
}

void Readdata()
{
    //freopen("loli.in","r",stdin);
    scanf("%d%d%d\n",&n,&m,&mod);
    for(int i=1;i<=m;i++)
        num[i]=getchar()-‘0‘;
}

void Close()
{
    fclose(stdin);
    fclose(stdout);
}

int main()
{
    Readdata();
    Make_Table();
    Solve();
    Close();
    return 0;
}