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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注