题目链接：https://contest.ucup.ac/contest/1356/problem/7187

题目大意：给一个长度为 $n$ 的字符串 $S$，问有多少个长度为 $m$ 的字符串满足所有真前缀没有子串等于 $S$ ，但整个串有。

做法 + 反思

看复杂度，应该是 $n\log$ 之类的东西，不大可能在 AC 自动机上跑，因此比较有可能的就是列一个线性递推式，然后常系数齐次线性递推。

我当时想到这一步了，可惜并没有列出线性递推式。

我当时的思路是，设 $g(m)$ 表示长度为 $m$ 的字符串且没有子串等于 $S$ ，然后在 $g(m-1)$ 放一个字符，容斥减去 $g(m-n)$ ，但 $g(m-n)$ 不一定满足前 $m-1$ 前缀没有子串等于 $S$ ，所以还得容斥，当时我的思路就是接着找 border ，不断下去，但是发现这个过程好想是无穷的。

例如 $S=aa$ 时，则按照这个思路可以得到：$g(m)=26g(m-1)-\sum\limits_{i=2}^{m}(-1)^ig(m-i)$ 。

下面的代码可以验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int N = 1e5 + 5;
LL f1[N][2], f2[N];
int n;
int main(){
    cin >> n;
    f1[0][0] = 1ll;
    for(int i = 1; i <= n; i++){
        f1[i][0] = (f1[i - 1][0] + f1[i - 1][1]) * 25ll % mod;
        f1[i][1] = f1[i - 1][0];
        cout << (f1[i][0] + f1[i][1]) % mod << " ";
    }
    cout << "\n";
    f2[0] = 1ll;
    for(int i = 1; i <= n; i++){
        f2[i] = f2[i - 1] * 26 % mod;
        for(int j = 2, type = -1ll; j <= i; j++, type = -type) f2[i] = (f2[i] + f2[i - j] * type + mod) % mod; 
        cout << f2[i] << " ";
    }
    cout << "\n";
    return 0;
}

然后我就觉得这个思路是错的，虽然上面的 $g(m)$ 可以加上 $g(m-1)$ ，这样就可以变成有限项求和，但是这只是针对 $S=aa$ 的情况，对于更加一般的情况，就不一定能这么干了，而且我也想不太明白一般情况下 $g$ 的递推式。（这个思路我感觉确实比较绕，比较难想）

但是如果换个角度来看：我们设 $f(m)$ 就表示答案，显然：$f(m)=26g(m-1)-g(m)$ ，上面的式子中，我们需要容斥掉不一定满足前 $m-1$ 前缀没有子串等于 $S$ 但是前 $m-n$ 的前缀满足的字符串，显然这就是 $\sum\limits_{Border}f(m-n+Border)$ 。

所以这显然就是 $\sum\limits_{Border}26g(m-n+Border-1)-g(m-n+Border)$ ，那么就得到了有限项的递推式。

然后直接加速一下，就可以在 $O(n\log{n}\log{k})$ 的时间解决这个问题了。

反思一下我为什么没做出来：我没找到有限项递推 ≠ 没有，我找到无限项递推 ≠ 没有有限项。

再回头看我那个思考方向，我不认为能想出来，从结果来看，有限项的递推式中一堆 $26$ ，因此可以知道那个无穷递推式的结果肯定很难看，更别说要看出怎样线性组合可以把那个无穷递推式变成有限项，反正我不认为那个角度可以想出来。

所以当推不出递推式的时候，先别着急的认为不存在递推式，或许换个方式去推就能很快推出来了。虽然做题的时候，做不出来换个方向考虑是正常的，但对于这种不同的推式子方法难度天差地别的方向，多换不同的方法推式子也是必要的。同理，组合题也是。

坑

代码？博主不会多项式算法，咕了，以后会了再回来补上。