洛谷 P3193

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

// 得到next函数
vector<int> getNext(string pattern)
{
    int m = pattern.size();
    vector<int> next(m,0);
    for(int i=1,j=0;i<m;i++)
    {
        while(j!=0 && pattern[i] != pattern[j]) j = next[j-1];
        if(pattern[j] == pattern[i]) j++;
        next[i] = j;
    }
    return next;
}

// 矩阵相乘函数
vector<vector<int>> matMul(vector<vector<int>> a,vector<vector<int>> b,int K)
{
    int m = a.size();
    vector<vector<int>> res(m,vector<int>(m,0)); //结果
    for(int i=0;i<m;i++) // i-k,k-j
    {
        for(int k=0;k<m;k++)
        {
            if(a[i][k]!=0) //剪枝减小工作量
            {
                for(int j=0;j<m;j++)
                {
                    res[i][j] = (res[i][j] + (ll)a[i][k] * b[k][j]) % K;
                }
            }
        }
    }
    return res;
}

// 矩阵幂函数(利用快速幂算法)
vector<vector<int>> matPow(vector<vector<int>> a,int p,int K)
{
    int m = a.size();
    vector<vector<int>> res(m,vector<int>(m,0)); //结果
    for(int i=0;i<m;i++) res[i][i] = 1; //单位矩阵用于起步
    while(p!=0)
    {
        if(p & 1) res = matMul(res,a,K);
        a = matMul(a,a,K);
        p >>= 1; // p /= 2
    }
    return res;
}

int main()
{
    int N,M,K;
    // M<=20 N<=1e9 K<=10000,所以不能暴力解
    cin >> N >> M >> K;
    string pattern; // 子串（此题中指的是不该出现的子串）
    cin >> pattern;

    // 求 pattern 的状态转移方程T[i][j]
    // 因为要用到pattern的next数组，所以先求next
    vector<int> next = getNext(pattern);
    vector<vector<int>> T(M,vector<int>(M,0)); // T[M][M],表示基础转移矩阵
    for(int m=0;m<M;m++) // m为当前匹配数量,由于不准出现匹配到完整M的，所以最大长度为M-1
    { 
        for(int digit=0;digit<=9;digit++) // 尝试每一个数字,从而进行状态转移
        {
            int cur = m; // 从当前位置开始回退
            while(cur!=0 && (pattern[cur]-'0') != digit) cur = next[cur-1];
            if((pattern[cur]-'0') == digit) cur++;
            if(cur < M) T[m][cur] = (T[m][cur] + 1) % K;
        }
    }

    // 得到完整的状态转移矩阵
    vector<vector<int>> Tn = matPow(T,N,K);

    ll result = 0;
    for(int i=0;i<M;i++)
    {
        result = (result + Tn[0][i]) % K;
    }

    cout << result << endl; 
    return 0;
}