解题 [HNOI2008] GT考试

题目：[HNOI2008] GT考试

阿申准备报名参加 GT 考试，准考证号为 \(N\) 位数\(X_1,X_2…X_n\ (0\le X_i\le 9)\)，他不希望准考证号上出现不吉利的数字。
他的不吉利数字\(A_1,A_2,\cdots, A_m\ (0\le A_i\le 9)\) 有 \(M\) 位，不出现是指 \(X_1,X_2\cdots X_n\) 中没有恰好一段等于 \(A_1,A_2,\cdots ,A_m\)，\(A_1\) 和 \(X_1\) 可以为 \(0\)。
阿申想知道不出现不吉利数字的号码有多少种，输出模 \(K\) 取余的结果。

对于全部数据，\(N\leq10^9\)，\(M\leq 20\)，\(K\leq1000\)。

这个题的做法是这样的：

这个题涉及到字符串匹配，题目中的“不出现”，也就代表着不吉利数字无法匹配到 \(m\)。

1、最暴力的想法是将准考证号枚举出来，然后在进行字符串匹配，这样的复杂度是 \(\mathcal O(10^N\times N)\) 的。

2、当使用 KMP 做字符串匹配的时候，我们可以考虑这样一个过程：

• 当 \(X\) 匹配到第 \(i\) 位，\(A\) 匹配到第 \(k\) 位，在下一个位置发生了失配。
• 然后跳 \(\text{border}\) 到下一个状态，\(X\) 匹配到第 \(i+1\) 位，\(A\) 匹配到第 \(j\) 位。

也就是由 \(q_i(k)+c\to q_{i+1}(j)\) 的转移。考虑到只需要求方案数，我们设 \(f_i(j)\) 为当 \(X\) 匹配到第 \(i\) 位，\(A\) 匹配到第 \(j\) 位的合法的号码的方案数（当然 \(j\) 永远不会等于 \(m\)）。

但是由 \(q_i(k)+c\to q_{i+1}(j)\) 的转移，会存在 \(0\) 或多种。那么考虑枚举字符 \(c\)，来得到“由位置 \(k\) 的下一个位置失配到位置 \(j\) 的方案数”，记为 \(g(k,j)\)。

for (int k = 0, j; k < m; k ++ )
	for (char c = '0'; c <= '9'; c ++ ) {
		for (j = nxt[k]; j && a[j + 1] != c; j = nxt[j]);
		g[k][j + (a[j + 1] == c)] ++;
	}

这样的话，就可以得到状态 \(f\) 的转移 \(f_i(j)\times g(j,k)\to f_{i+1}(k)\)。

那么根据 \(f\) 的定义来看，就可以达到最终答案 \(\sum_{i=0}^{m-1}f_n(i)\)，总时间复杂度为 \(\mathcal O(nm^2)\)。

参考代码（\(40\text{ pts}\)）：

#include <bits/stdc++.h>

using namespace std;

int n, m, K, ans, nxt[21], g[21][21], dp[10010][21];
char a[21];

int main() {
	cin >> n >> m >> K >> (a + 1);
	
	for (int i = 2, j = 0; i <= m; i ++ ) {
		for (j = nxt[i - 1];j && a[j + 1] != a[i]; j = nxt[j]);
		nxt[i] = a[j + 1] == a[i] ? j + 1 : 0;
	}
	
	for (int i = 0, j; i < m; i ++ ) {
		for (char c = '0'; c <= '9'; c ++ ) {
			for (j = i; j && a[j + 1] != c; j = nxt[j]);
			g[i][j + (a[j + 1] == c)] ++;
		}
	}
	
	dp[0][0] = 1;
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 0; j < m; j ++ ) {
			for (int k = 0; k < m; k ++ ) {
				dp[i][j] = (dp[i - 1][k] * g[k][j] + dp[i][j]) %K;
			}
		}
	}
	
	for (int i = 0; i < m; i ++ ) ans = (ans + dp[n][i]) %K;
	cout << ans << '\n';
	return 0;
}

3、优化转移

分析状态 \(f\) 的转移 \(\sum_{i=0}^{m-1}f_i(j)\times g(j,k)\to f_{i+1}(k)\)，从中可以得到 \(f_i(1,j)\times g(j,k)\to f_{i+1}(1,k)\)，即一个矩乘的式子 \(f_i\times g=f_{i+1}\)。

然后对转移进行矩阵加速幂，时间复杂度为 \(\mathcal O(m^3\log_2n)\) 的。

参考代码（\(100\text{ pts}\)）：

#include <bits/stdc++.h>
using namespace std;


const int M = 31;

int n, m, K, res, nxt[M];

char s[M];

struct matrix {
    int a[M][M], n, m;
    matrix() {
        n = m = 0;
        memset(a, 0, sizeof(a));
    }
} F, G;

matrix operator* (const matrix &a, const matrix &b) {
    matrix tmp;
    tmp.n = a.n, tmp.m = b.m;
    for (int i = 0; i < tmp.n; i ++ ) {
        for (int j = 0; j < tmp.m; j ++ ) {
            for(int k = 0; k < a.m; k ++ ) {
                tmp.a[i][j] = (tmp.a[i][j] + a.a[i][k] * b.a[k][j] %K) %K;
            }
        }
    }
    return tmp;
}

matrix Power(matrix a, int k) {
    matrix ans = a; 
    for (k --; k; a = a * a, k >>= 1)
        if (k & 1) ans = ans * a;
    return ans;
}

int main()
{
    cin >> n >> m >> K >> (a + 1);
    
    F.n = 1, F.m = G.m = G.n = m;

    for (int i = 2, j = 0; i <= m; i ++ ) {
		for (j = nxt[i - 1];j && a[j + 1] != a[i]; j = nxt[j]);
		nxt[i] = a[j + 1] == a[i] ? j + 1 : 0;
	}
	
	for (int i = 0, j; i < m; i ++ ) {
		for (char c = '0'; c <= '9'; c ++ ) {
			for (j = i; j && a[j + 1] != c; j = nxt[j]);
			g[i][j + (a[j + 1] == c)] ++;
		}
	}

    F.a[0][0] = 1;

    F = F * Power(G, n);

    for (int i = 0; i < m; i ++ ) res = (res + F.a[0][i]) %mod; 

    cout << res << '\n';
    return 0;
}