自动搬运

查看原文

来自洛谷，原作者为

	Edgration **

搬运于2025-08-24 21:46:20，当前版本为作者最后更新于2018-04-12 23:00:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解有点长请耐心观看...

题意

求有多少个$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;
}