1. 题目

给出一个长度为 $m$的字符串（由 0~9 构成）

求不包含该子串（连续子串）的长度为 $n$的字符串个数（由 0~9 构成），答案对 $k$取模。

$n\leq 10^3,M\leq 20,k\leq 1000$

2. 题解

谢谢 ABS 同学教我这题啦～

先对给出的字符串跑一遍 Kmp 求出其 next 数组。

然后设 $f[i,j]$已经构造的字符串（长度为 $i-1$）的后缀与模式串的前缀的最长公共长度为 $j$时，构造 $[i, n]$的方案数。

对于 $f[i,j]$枚举第 $i$个字符，若与模式串的第 $j+1$个字符相同则从 $f[i+1,j+1]$转移状态，否则说明失配，从 $f[i+1,nxt[…]]$转移状态。这里的 $nxt[…]$指的是 nxt 一直根据模式串的 nxt 数组跳，直到跳到某个位置，比如是 $nxt[x]$，使得模式串的 $nxt[x]+1$个字符与当前枚举的字符相同。也有可能一直失配，那么 $nxt[…]$就是 0 了。这个和 Kmp 匹配字符串是相同的。

这样复杂度是 $O(n^3)$的。

其实还可以与处理一下 $pre[i,c]$表示当前匹配了 $i$个，然后当前要填 $c$，会跳到哪里去。这个预处理是 $O(n^2)$的，然后再跑 Dp 也是 $O(n^2)$的了。

代码 ($O(n^3)$)：

#include <bits/stdc++.h>

#define NS (1005)

using namespace std;

int n, m, k, nxt[NS], f[NS][NS];

char str[NS];

void Kmp()
{
    for (int i = 2, j = 0; i <= m; i += 1)
    {
        while (j && str[j + 1] != str[i]) j = nxt[j];
        if (str[j + 1] == str[i]) j++;
        nxt[i] = j;
    }
}

int Dp(int a, int b)
{
    if (b == m) return 0;
    if (a > n) return 1;
    if (f[a][b] != -1) return f[a][b];
    int& F = f[a][b]; F = 0;
    for (char c = '0'; c <= '9'; c += 1)
    {
        if (c == str[b + 1]) F += Dp(a + 1, b + 1);
        else
        {
            int j = nxt[b];
            while (j && c != str[j + 1]) j = nxt[j];
            if (c == str[j + 1]) j++;
            F += Dp(a + 1, j);
        }
        F %= k;
    }
    return F;
}

int main(int argc, char const* argv[])
{
    scanf("%d%d%d%s", &n, &m, &k, str + 1), memset(f, -1, sizeof(f));
    Kmp(), printf("%d\n", Dp(1, 0));
    return 0;
}