题解 P3193 【[HNOI2008]GT考试】

题解有点长请耐心观看... ## 题意 求有多少个$n$位的数字串不包含$m$位的字符串 （范围 $n <= 1e9 $， $m <= 20$） ## 分析 网上的题解我都看不懂啊QAQ(太弱了)，那么我就写详细一点吧... ### 0x01 暴力 第一眼看到就是不会... 不会怎么办..先把暴力打了... 暴力枚举字符串，然后$Hash$比较 复杂度$O(10^n\cdot n)$，实测只能过$n<=7$的点 然后得到$10$分  ### 0x02 DP 妈妈我会$DP$ ! 根据套路，因为$m$并不会很大，设$f[i][j]$表示长串匹配到第$i$位，短串最多可以匹配到第$j$位的方案数  那么为了让它不能找到完全的匹配，答案就是 $$\sum_{i=0}^{m-1}f[n][i]$$ 那么怎么转移？ 考虑对于已经匹配了的$f[i][j]$转移到$f[i + 1][k]$新加一个新的字符造成的影响。  由于这个$new$是可以随便填写的，对于短串的$j+1$，可能会有几种情况。 1. new和$t+1$匹配，转移到$f[i+1][j+1]$ 2. 不匹配  如图，这样可能会找到一个新的长度为$k$的前缀使得和当前枚举到的后缀匹配  甚至$k=0$无法匹配 其实，这个东西和枚举的字母无关，考虑到最后的答案，在$DP$过程中只需要考虑长度对答案造成的影响。 对于这一点，我们就是要知道，对于一个匹配到长度为$j$的串，转移到$k$的串的方案，也就对于长度为$i$的串，加一个数子，能加入多少种数字，使得长度为$j$的匹配变成长度为$k$的匹配（如图）。 $DP$式就可以写出来啦 $$f[i][j]=\sum_{k=0}^{m-1} f[i-1][k]*g[k][j]$$ $DP$套$DP$？ 其实没那么麻烦，对于第二个的方案数，因为我们知道短串，这个“$g[i][j]$”是固定的，就可以预处理出结果。  为了计算长度为$j$的已经匹配好了的串可以用多少种数字变为$k$，枚举一个数字，看它在短串中最长可以匹配到最多多长的前缀。 妈妈我会$Kmp$！ 然后为了保证是最长的而且前面的东西保留，暴力枚举的复杂度好像有点爆炸，这个时候一看不就是一个裸$Kmp$吗，对于新的数字，失去匹配就跳$next$。  于是就得到了一个$O(n*m^2)$的优秀算法.... 大概可以做$n<=250000$的数据，然后得到$40$分  ### 0x03 矩阵快速幂 然后看一看$DP$式 $$f[i][j]=\sum_{k=0}^{m-1} f[i-1][k]*g[k][j]$$ 这不就是一个矩阵乘法的式子吗... 因为$g[i][j]$是固定的，于是把$f[i][j]$看成一个矩阵，对于矩阵$F[i]$它的第一层就是$f[i][j]$。 $$F[i]=F[i-1]*G$$ $G$是固定的，你又知道$F[0]$的第一行第一列是$1$，然后求一个$F[n]$就行了... 矩阵快速幂即可.... ### 0x04 代码 暴力 ``` #include<bits/stdc++.h> using namespace std; inline int read(){ char ch = getchar(); int u = 0, f = 1; while (!isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); } while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); } return u * f; } const int maxn = 1e5 + 10; int n, m, k; int ans = 0; typedef unsigned long long ull; ull ha_m; ull mod = 19260817; ull base = 266; ull ha[maxn], pw[maxn]; int s[maxn]; char md[maxn]; inline void build(){ ha[0] = 0; for (int i = 1; i <= n; ++i) ha[i] = (ha[i - 1] * base + s[i]) % mod; } inline ull split(int l, int r){ return ((ha[r] - (ha[l - 1] * pw[r - l + 1]) % mod) + mod) % mod; } inline void dfs(int x){ if (x == n + 1){ build(); for (int i = 1; i + m - 1 <= n; ++i){ if (split(i, i + m - 1) == ha_m) return; } ans++; return; } for (int i = 0; i <= 9; ++i){ s[x] = i; dfs(x + 1); } } int main(){ // freopen("data.txt", "r", stdin); n = read(), m = read(), k = read(); if (n >= 10) return 0 * puts("NO"); scanf("%s", md + 1); pw[1] = base; for (int i = 2; i <= n; ++i) pw[i] = (pw[i - 1] * base) % mod; for (int i = 1; i <= m; ++i) ha_m = (ha_m * base + (md[i] - '0')) % mod; dfs(1); printf("%d", ans % k); return 0; } ``` 40分DP ``` #include<bits/stdc++.h> using namespace std; inline int read(){ char ch = getchar(); int u = 0, f = 1; while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); } return u * f; } const int maxn = 1e6+10; int f[maxn][30], n, m, k; int nxt[50], match[50][50]; char md[50]; inline void Inittt(){ n = read(), m = read(), k = read(); scanf("%s", md + 1); } inline void Kmp(){ nxt[0] = -1; for (int i = 1; i <= m; ++i){ int j = nxt[i - 1]; while (j != -1 && md[j + 1] != md[i]) j = nxt[j]; nxt[i] = j + 1; } nxt[0] = 0; for (int i = 0; i < m; ++i){ for (int j = '0'; j <= '9'; ++j){ int temp = i; while (md[temp + 1] != j && temp > 0) temp = nxt[temp]; if (md[temp + 1] == j) temp++; if (temp < m) match[i][temp]++; } } } int main(){ Inittt(); Kmp(); f[0][0] = 1; for (int i = 1; i <= n; ++i) for (int j = 0; j < m; ++j) for (int p = 0; p < m; ++p) { (f[i][j] += f[i - 1][p] * match[p][j]) %= k; } int ans = 0; for (int i = 0; i < m; ++i) (ans += f[n][i]) %= k; printf("%d", ans); return 0; } ``` 100分代码（人傻大常数大 ``` #include<bits/stdc++.h> using namespace std; inline int read(){ char ch = getchar(); int u = 0, f = 1; while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); } return u * f; } const int maxn = 5050; int f[maxn][30], n, m, k; int nxt[maxn], match[maxn][50]; char md[maxn]; inline void Kmp(){ nxt[0] = -1; for (int i = 1; i <= m; ++i){ int j = nxt[i - 1]; while (j != -1 && md[j + 1] != md[i]) j = nxt[j]; nxt[i] = j + 1; } nxt[0] = 0; for (int i = 0; i < m; ++i){ for (int j = '0'; j <= '9'; ++j){ int temp = i; while (md[temp + 1] != j && temp > 0) temp = nxt[temp]; if (md[temp + 1] == j) temp++; if (temp < m) match[i][temp]++; } } } class MARTIX{ public: int mr[23][23]; MARTIX(){ memset(mr, 0, sizeof(m)); } void pr(){ for (int i = 0; i <= m; i++, cerr << endl) for (int j = 0; j <= m; ++j) cerr << mr[i][j] << " "; } MARTIX operator * (MARTIX B){ MARTIX Rtn; memset(Rtn.mr, 0, sizeof(Rtn.mr)); for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) for (int p = 0; p < m; ++p) { (Rtn.mr[i][j] += mr[i][p] * B.mr[p][j]) %= k; } return Rtn; } }F, G; inline MARTIX ksm(MARTIX A, int pw){ MARTIX Rtn; for (int i = 0; i <= m; ++i) Rtn.mr[i][i] = 1; for (; pw; pw >>= 1, A = A * A) if (pw & 1) Rtn = Rtn * A; return Rtn; } signed main(){ n = read(), m = read(), k = read(); scanf("%s", md + 1); Kmp(); F.mr[0][0] = 1; for (int i = 0; i <= m; ++i) for (int j = 0; j <= m; ++j) G.mr[i][j] = match[i][j]; G = ksm(G, n); F = F * G; int ans = 0; for (int i = 0; i < m; ++i) { (ans += F.mr[0][i]) %= k; } printf("%d", ans); return 0; } ```