题解：P3193 [HNOI2008] GT 考试

题目

阿申准备报名参加 GT 考试，准考证号为 位数，他不希望准考证号上出现不吉利的数字。
他的不吉利数字 有 位，不出现是指 中没有一段恰好等于 ， 和 可以为 。

阿申想知道不出现不吉利数字的号码有多少种，输出模 取余的结果。

数据范围及约定

对于全部数据，，，。

心路历程

1. 看到题面就想暴力，每一步可以填写 个数字，然后每次 check() 一下 有没有匹配上；
   此时 int dfs(int cur, int match) 就是记录“第几位、结尾匹配上了几个时的方案数”；

2. 考虑加记忆化，改成 DP；
   发现对于一个 cur, match 一定的时候调用的是同一个函数；
   所以就用 表示前 位结尾匹配上 个的方案数；

3. 意识到出现了错误。
   因为我的 dfs 过程中，分为“继续匹配，匹配断掉”两种情况，而后者我 match 直接归零了；
   然后发现这应该是一个 的 fail[] 跳转的过程；（我沿用 自动机的命名方式）
   看看在 cur 失配的时候匹配上的最长长度；

4. 这个时候用了 分钟左右，还是比较快速的，就进入到了优化环节；
   首先是把记忆化搜索写成递推的版本，因为 的数据是不能线性推的，只能加速递推；
   于是改成了递推版本并且交了一发：

   f[0][0] = 1;
   for (int i = 1; i <= n; ++i) {
       for (int j = 0; j < m; ++j)
           for (int num = 0; num <= 9; ++num) {
               int ind = j;
               while (ind && a[ind + 1] - '0' != num)
                   ind = fail[ind];
               if (a[ind + 1] - '0' == num)
                   ind++;
               if (ind < m) {
                   f[i][ind] = (f[i][ind] + f[i - 1][j]) % k;
   //              printf("transform:\tfrom%d\t->\t%d\n", j, ind);  
               }
           }
   //  system("pause");
   }

   此时拿下 40pts 的小数据分，然后我发现可以用滚动数组，因为只依赖上一行；
   但是我有更大的发现：

5. 如果你尝试写下类似注释的内容，会发现对于每一个 ，它的转移是一定的；
   也就是说，状态转移的方式，对 来说是个定值，只与 有关；
   聪明的你一定想到可以写作一个矩阵了；

6. 就在此时我发现矩阵加速和普通递推的微妙关系：
   只要把递推程序中 f[][] = ... 改成 matrix[][] += ... 就是矩阵的生成方式；
   而原来滚动数组优化之后的一行，就是我们的答案向量；
   （我喜欢用行向量，大家为什么都是列？）
   而写成向量形式，本身就是反复以来，滚动贡献的一个过程；
   不过矩阵加速又把递推过程本身分离开来，计算出每个初始值对最终答案的贡献是什么；

7. 然后的步骤非常简单，
   写 struct，写 Pow，
   把内层搬出去生成 sol 矩阵，用 vec 乘起来，
   统计 vec 内的答案；
   然后恭喜我自己 掉了；

8. 这很正常，我习惯了，
   我回头检查 fail[] 的板子有没有打错，我自己再造了一个数据，发现 fail 正确；
   我回头检查 sol[][] 矩阵有没有生成错误，我用刚刚的 40pts 程序对拍，发现正确；
   问题只能出在 vec 答案向量上了，然而他的初始化是对的，vec[0][0] = 1；

9. 约 30mins 以后我开始生气了，我已经坐不住了，浑身发抖；
   我走来走去，用手捶自己的腿；
   我很疑惑，很生气，看了一眼我的 struct Matrix，检查了矩阵乘法的下标，是正确的；

   然后惊喜的发现，我把 * 打成 + 了！

10. 后来的故事，我把它改了之后一发 AC；
    然后应该也有同学听到我在那边大喊大叫，在这里诚挚的道歉；
    没办法，人把自己蠢到了就是会这样；

题解

大部分内容在“心路历程”都讲过了，但是写给那些认真做题追求效率不喜欢看唐人小故事的人看。

Step 1

• 考虑暴力尝试 填入，并且检查是否已经完全匹配了，如果是就 return 0;；
• 发现之前匹配了一部分的地方不重要，只有结尾才能够扩展到整个；
• 所以检查匹配的方式就是记录一个变量 match 表示已经匹配了多长了；
• 最后一直存活到 cur = n + 1 位置就说明可行解， return 1;；

Step 2

• 填入数字的时候会有失配现象，我们需要知道此时又匹配上了多少，而不是归零；
  这个操作正是 的精髓：fail[] 跳转；
• 发现对于同一个 cur, match 调用同一个递归函数，对于此加记忆化 ；
• 写作递推的形式，输出一下发生转移的位置，发现递推关系仅由 决定；
  对于 而言等效为一个固定的递推方式；
• 结合数据量，望矩阵加速的方向靠，想到需要用 fail[] 结合生成递推矩阵；

Step 3

• 你都已经把递推矩阵写出来了，已经无需多盐。

代码：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2005;
const int MAXM = 25;

int n, m, k;

struct Matrix {
    int lenRow;
    int lenCol;
    vector< vector<int> > mat;
    
    inline void resize(int row, int col) {
        lenRow = row;
        lenCol = col;
        mat.resize(row, vector<int>(col, 0));
        return;
    }
    inline bool reset() {
        if (lenRow != lenCol)
            return false;
        for (int i = 0; i < lenRow; ++i)
            mat[i][i] = 1;
        return true;
    }
    inline Matrix operator * (Matrix ano) const {
        Matrix res;
        res.resize(lenRow, ano.lenCol);
        for (int i = 0; i < res.lenRow; ++i)
            for (int j = 0; j < res.lenCol; ++j)
                for (int x = 0; x < ano.lenRow; ++x)
                    res.mat[i][j] = (res.mat[i][j] + mat[i][x] * ano.mat[x][j]) % k;
        return res;
    }
};

int lenA;
string a;
int fail[MAXM];

int f[MAXN][MAXM];

inline void calcFail() {
    fail[1] = 0;
    for (int cur = 2; cur <= lenA; ++cur) {
        int pre = fail[cur - 1];
        while (pre && a[cur] != a[pre + 1])
            pre = fail[pre];
        if (a[cur] == a[pre + 1])
            pre++;
        fail[cur] = pre;
    }
    return;
}

inline Matrix Pow(Matrix base, int expo) {
    Matrix res = base;
    expo--;
    while (expo) {
        if (expo & 1)
            res = res * base;
        base = base * base;
        expo >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n >> m >> k;
    
    cin >> a;
    lenA = a.size(), a = " " + a;
    calcFail();
    
    Matrix sol;
    sol.resize(m, m);
    for (int i = 0; i < m; ++i)
        for (int cur = 0; cur <= 9; ++cur) {
            int ind = i;
            while (ind && a[ind + 1] - '0' != cur)
                ind = fail[ind];
            if (a[ind + 1] - '0' == cur)
                ind++;
            if (ind < m)
                sol.mat[i][ind]++;
        }
    
    Matrix vec;
    vec.resize(1, m);
    vec.mat[0][0] = 1;
    
    sol = Pow(sol, n);
    vec = vec * sol;
    int ans = 0;
    for (int i = 0; i < m; ++i)
        ans = (ans + vec.mat[0][i]) % k;
    cout << ans;
    return 0;
}