基础数学算法-GT考试(KMP + 矩阵乘法 + DP)

题目-GT考试

问题分析

要求生成字符串并且不包含$s$, 求方案数量
数据范围$N\le 50$的时候, 参考基础动态规划问题(1)的设计密码问题, 状态转移方程是$f(i+1,k)=f(i+1,k)+f(i,j)$

但是发现本题的数据范围是$10^9$, 上述做法的时间复杂度是$O(nm)$, 一定会超时的, 需要进行优化

• 考虑状态表示$f(i,j)$表示, 生成了长度为$i$的字符串, 并且不包含串$s$, 并且与$s$匹配的最长公共前后缀长度是$j$的一类字符串, 属性是$cnt$

• 假设当前状态是$f(i,j)$, 那么在当前字符串结尾加入一个字符$c$, 看KMP算法的$j$指针($j=ne[i-1]$)能指向什么位置, 假设是$k$, 也就是s[k] == c, 那么

$$f(i+1,k)=f(i+1,k)+f(i,j)$$

$m$是$s$的长度, 将所有式子展开($j$指针指向$m$的时候匹配上, 因此最远只能指向$m-1$位置)

$$f(i+1,0)=a_{0,0}f(i,0)+a_{0,1}f(i,1)+...+a_{0,m-1}f(i,m-1)$$
$$f(i+1,1)=a_{1,0}f(i,0)+a_{1,1}f(i,1)+...+a_{1,m-1}f(i,m-1)$$
$$\begin{gathered} f(i+1,2)=a_{2,0}f(i,0)+a_{2,1}f(i,1)+...+a_{2,m-1}f(i,m-1) \\ ⋮ \end{gathered}$$

关键点:
假设$f(i,j)$的方案数是$x$, 状态机从$j$转移到$k$的方案数是$y$, 那么$f(i+1,k)$需要累加$x\times y$的方案数
$$f(i+1,k)=\sum f(i,j)\times t$$
$t$是状态机从$j$转移到$k$的方案数

令$F(i)=[f(i,0),f(i,1),...,f(i,m-1)]$, 那么有$F(i+1)=F(i)\times A$
其中
A = [ 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 ] A = \left[\begin{array}{cccc} a_{0,0} & a_{0,1} & \ldots & a_{0, m-1} \\ a_{1,0} & a_{1,1} & \ldots & a_{1, m-1} \\ \ldots & \ldots & \ldots & \ldots \\ a_{m-1,0} & a_{m-1,1} & \ldots & a_{m-1, m-1} \end{array}\right] A= ​a0,0​a1,0​…am−1,0​​a0,1​a1,1​…am−1,1​​…………​a0,m−1​a1,m−1​…am−1,m−1​​ ​

可以将动态规划的过程使用矩阵乘法进行优化, 原来递推计算的$F_n$, 可以在$\log n$复杂度内算出

算法步骤

• 首先预处理KMP算法的$ne$数组
• 构建自动机, 计算$A(i,j)$, 如果$j$能转移到$k$, 那么$A(j,k)=A(j,k)+1$
• 初始状态$F_0=[1,0,0,...,0]$, 快速幂计算$F_n$
• 实现矩阵快速幂算法

算法时间复杂度$O(m\log n)$

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int n, m, mod;
string s;
int ne[N], A[N][N];

void init() {
   
    for (int i = 1; i < m; ++i) {
   
        int j = ne[i - 1];
        while (j && s[j] != s[i]) j = ne[j - 1];
        if (s[j] == s[i]) ne[i] = j + 1;
    }

    for (int j = 0; j < m; ++j) {
   
        for (char c = '0'; c <= '9'; ++c) {
   
            int k = j;
            while (k && s[k] != c) k = ne[k - 1];
            if (s[k] == c) k++;
            if (k < m) A[j][k] = (A[j][k] + 1) % mod;
        }
    }
}

void mul(int c[], int a[], int b[][N]) {
   
    static int tmp[N];
    memset(tmp, 0, sizeof tmp);

    for (int i = 0; i < m; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            tmp[i] = (tmp[i] + a[j] % mod * b[j][i] % mod) % mod;
        }
    }

    memcpy(c, tmp, sizeof tmp);
}

void mul(int c[][N], int a[][N], int b[][N]) {
   
    static int tmp[N][N];
    memset(tmp, 0, sizeof tmp);

    for (int i = 0; i < m; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            for (int k = 0; k < m; ++k) {
   
                tmp[i][j] = (tmp[i][j] + a[i][k] % mod * b[k][j] % mod) % mod;
            }
        }
    }

    memcpy(c, tmp, sizeof tmp);
}

// F[n] = F[0] * A ^ n
void solve() {
   
    int f0[N] = {
   0};
    f0[0] = 1;

    int k = n;
    while (k) {
   
        if (k & 1) mul(f0, f0, A);
        mul(A, A, A);
        k >>= 1;
    }

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

    cout << ans << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> mod;
    for (int i = 0; i < m; ++i) {
   
        char c;
        cin >> c;
        s += c;
    }

    init();
    solve();

    return 0;
}