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

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

做法 + 反思

看复杂度，应该是 nlog 之类的东西，不大可能在 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)−∑i=2m(−1)ig(m−i) 。

下面的代码可以验证：

cpp
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 的前缀满足的字符串，显然这就是 ∑Borderf(m−n+Border) 。

所以这显然就是 ∑Border26g(m−n+Border−1)−g(m−n+Border) ，那么就得到了有限项的递推式。

然后直接加速一下，就可以在 O(nlog⁡nlog⁡k) 的时间解决这个问题了。

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

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

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

坑

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