Luogu P4548 [CTSC2006]歌唱王国

题目描述

https://www.luogu.com.cn/problem/P4548

简要题意：给定 $m$ 个字符串 $S_i$，字符集为 $[1,n]$，现在要求对于每个字符串 $S_i$ 进行如下操作：从空串 $T$ 开始，每次随机生成一个 $[1,n]$ 内的整数，添加到 $T$ 的末尾，直到 $S$ 作为 $T$ 的子串出现过，求 $T$ 的期望长度

$|S_i|,n\le 10^5,m\le 50$

Solution

我们令 $f_i$ 表示 $T$ 的长度为 $i$ 的概率，$g_i$ 表示 $T$ 的长度大于 $i$ 的概率，分别令 $F(x)$ 和 $G(x)$ 为 $f_i$ 和 $g_i$ 的生成函数

容易得到 $F(x)+G(x)=1+xG(x)$ 这个等式，可以理解其为没有停止时，我们再加入一个字符，有停止和继续两种情况，加一是处理边界情况

同时，我们可以得到另一个等式 $G(x)(\frac{1}{n}x)^m=F(x)\sum_{i=1}^na_i(\frac{1}{n}x)^{m-i}$，这里我们令 $m$ 表示字符串 $S$ 的长度 $a_i$ 表示 $S[1..i]$ 是否为 $S$ 的 $border$，这个等式可能理解起来有一点难度，我们可以理解其为没有停止的串加入 $S$ 之后一定会停止，但注意到可能会在完整添加 $S$ 之前停止，这种情况只有在 $S[1..i]$ 是 $S$ 的 $border$ 的情况下，我们添加了 $S[1..i]$ 就已经停止了

我们考虑利用这两个式子来得到我们所需要的答案，即 $F’(1)$

我们对第一个式子求导并带入 $x=1$，可以得到 $F’(1)=G(1)$，在第二个式子里带入 $x=1$ 并化简可以得到 $G(1)=\sum_{i=1}^m a_in^i$

时间复杂度 $O(n)$

#include <iostream>
#include <iomanip>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 10000;

int nxt[maxn]; 
void init_nxt(int *s, int l) {
    int k = 0; nxt[1] = 0; 
    for (int i = 2; i <= l; ++i) {
        while (k && s[k + 1] != s[i]) k = nxt[k];
        if (s[k + 1] == s[i]) ++k;
        nxt[i] = k;
    }
}

int n, m, a[maxn];
ll pn[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    pn[0] = 1; for (int i = 1; i <= 100000; ++i) pn[i] = pn[i - 1] * n % p; 
    for (int o = 1; o <= m; ++o) {
        int len; ll ans = 0; cin >> len;
        for (int i = 1; i <= len; ++i) cin >> a[i];
        init_nxt(a, len); int t = len;
        while (t) ans = (ans + pn[t]) % p, t = nxt[t];
        cout << setw(4) << setfill('0') << ans << "\n";
    }
    return 0;
}