分析

• 这一题是AcWing 1052. 设计密码的一道扩展题目，分析方式仍然是动态规划。扩展方式是数据量，AcWing 1052. 设计密码中的n值最大为50，这里的n最大可以取到$10 ^ 9$。这是一种扩展方式，还有另外一种扩展方式，不扩展n，而是让不能包含多个字符串，对应题目是：AcWing 1053. 修复DNA，可以使用AC自动机解决。

• 本题的分析如下：

• 通过上面的分析，我们根据状态计算可以得到第i层和第i+1层之间的关系，即

$$ f(i+1, 0) = a_{0,0} \times f(i, 0) + a_{1,0} \times f(i, 1) + … + a_{m-1,0} \times f(i, m - 1) \\\\ f(i+1, 1) = a_{0,1} \times f(i, 0) + a_{1,1} \times f(i, 1) + … + a_{m-1,1} \times f(i, m - 1) \\\\ … \\\\ f(i+1, m-1) = a_{0,m-1} \times f(i, 0) + a_{1,m-1} \times f(i, 1) + … + a_{m-1,m-1} \times f(i, m - 1) $$

如果我们令：
$$ F(i+1) = [f(i+1, 0), f(i+1, 1), …, f(i+1, m-1)] \\\\ A = \left[ \begin{matrix} a_{0,0} & a_{0,1} & … & a_{0,m-1} \\\\ a_{1,0} & a_{1,1} & … & a_{1,m-1} \\\\ … & … & … & … \\\\ a_{m-1,0} & a_{m-1,1} & … & a_{m-1,m-1} \end{matrix} \right] $$
则有：
$$ F(i+1) = F(i) \times A $$
展开为：
$$ [f(i+1, 0), f(i+1, 1), …, f(i+1, m-1)] = \\\\ [f(i, 0), f(i, 1), …, f(i, m-1)] \times \left[ \begin{matrix} a_{0,0} & a_{0,1} & … & a_{0,m-1} \\\\ a_{1,0} & a_{1,1} & … & a_{1,m-1} \\\\ … & … & … & … \\\\ a_{m-1,0} & a_{m-1,1} & … & a_{m-1,m-1} \end{matrix} \right] $$

• 根据上面的分析可知，矩阵A只与不合法串S有关，因此A矩阵是不变的。根据上面递推式可知：

$$ F(n) = F(0) \times A ^{n} \quad \quad F(0) = [1, 0, 0, …] $$

• 如何求解数组A呢？如果从f(i, j)可以转移到f(i+1, k)，则让a[j, k]++。即让f(i+1, k) += f(i, j)：

$$ f(i+1, k) = a_{0,k} \times f(i, 0) + a_{1,k} \times f(i, 1) +… + a_{j,k} \times f(i, j) + … + a_{m-1,k} \times f(i, m - 1) $$

• 求出向量F(n)后，最后的答案就是向量F(n)中所有的元素之和。

• 这是一类问题，凡是动态规划中两层之间的转移形式是乘以一个固定矩阵的，都可以使用快速幂优化。

分析

#include <iostream>
#include <cstring>

using namespace std;

const int N = 25;

int n, m, mod;  // 准考证号为 n 位数, 不吉利数字为m位
char str[N];  // 不吉利数字串
int ne[N];  // KMP求str自身的ne
int a[N][N];  // 转移矩阵

void mul(int c[][N], int a[][N], int b[][N]) {

    static int t[N][N];
    memset(t, 0, sizeof t);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % mod;
    memcpy(c, t, sizeof t);
}

int qmi(int k) {

    int f0[N][N] = {1};
    while (k) {
        if (k & 1) mul(f0, f0, a);  // f0 = f0 * a
        mul(a, a, a);  // a = a * a;
        k >>= 1;
    }

    int res = 0;
    for (int i = 0; i < m; i++) res = (res + f0[0][i]) % mod;
    return res;
}

int main() {

    cin >> n >> m >> mod;
    cin >> str + 1;

    // KMP
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && str[i] != str[j + 1]) j = ne[j];
        if (str[i] == str[j + 1]) j++;
        ne[i] = j;
    }

    // 初始化A[i][j]
    for (int j = 0; j < m; j++)
        for (int c = '0'; c <= '9'; c++) {
            int k = j;  // 原字符串后缀和str前缀匹配的长度
            while (k && str[k + 1] != c) k = ne[k];
            if (str[k + 1] == c) k++;
            if (k < m) a[j][k]++;
        }

    // F[n] = F[0] * A^n
    cout << qmi(n) << endl;

    return 0;
}