题目
给出一个长度为(n)的串(s)，询问有多少个长度为(m)的串(t)
满足 (t) 的无限循环串存在一个长度为(n)且比(s)字典序严格小的子串
$ n , m le 2000 $
题解
-
自从CTS打铁之后就非常自闭，智商一天不如一天，所以感觉这题异常抽象。。。
我看的这位神仙的题解
-
Part 1
考虑统计任意字串都大于等于的数量然后减去，首先对 $ s $ 建立 $ kmp $ 自动机
由于题目中的限制，结点 $ i $ 的出边不能比 $ i+1,nxt[i]+1,nxt[nxt[i]]+1,cdots $ 位字符((fail)链上的后一位)小
只要能在这样的自动机上走无限多次 (t) ,那么串 (t) 就是合法的
考虑状态((i,j))表示自动机在结点(i)时，构造到了 (t) 的对应第(j)位
不同((i,j))的数量也是有限的，那么一旦第二次到某个 $ (i,j) $ 的时候就出现了循环节
考虑循环节的长度为(l) ，显然有 (l) 要么是(|s|) 的倍数(1)，要么是(|s|)的因数(2)
到达((i,j))的最后一次一定是失配的，否则可以把循环节的起点向前移动
从 (i) 开头的是 (t) 的一个循环位移 (t') , 现在如果是情况(1)，设循环节为(kt’(k>1))，说明(s_{1,i} + kt')有一个更小的循环节(t’),那么显然有一个更小的循环节长度为 (|t'|)
所以在有限步会走到一个环，且(l)满足(2)，那就在环里不出来了=O^O=
所以一个串一定可以映射到一个环
-
Part 2
进一步考虑题目中的限制，相当于只有最小的那条边可能连向某个非0位置，其它的边一定连向0
记这两种边为实边和虚边，如果(i)的实边不连向(i+1)，那么 (i+1) 到 (n) 就都不连通，没用了
所以自动机类似这样一个( ho)形
-
Part 3
-
分开计数，考虑单独末尾的环
如果长度为(m)的因数那么就可以贡献长度个不同的串，否则不贡献答案
-
考虑经过0的环
最后的环一定是所有环在0的组合
一种顺序的环贡献就是最后一个环的长度，可以枚举一个最后一个环上的点
(f_{i,j})表示从 (0) 走 (i) 步到 (j) 的方案，(g_{i,j}) 表示从 (j) 经 (i) 步沿黑边跳回 (0) 的方案
所以 (ans = sum _{i=0}^{m} sum_{j=0}^{n} f_{i,j} imes g_{m-i,j})
-
-
暂时不会$n log n $的多项式解法
#include<bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
const int N=2010;
int n,m,nxt[N],to[N],mx[N],f[N][N],g[N][N],len,pw=1;
char s[N];
void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}
int main(){
// freopen("repeat.in","r",stdin);
// freopen("repeat.out","w",stdout);
scanf("%d%s",&m,s+1);n=strlen(s+1);
for(int i=1;i<=m;++i)pw=(ll)pw*26%mod;
for(int i=2,j=0;i<=n;nxt[i++]=j){
while(j&&s[i]!=s[j+1])j=nxt[j];
if(s[i]==s[j+1])++j;
}
for(int i=0;i<=n;++i){
int k=i==n?nxt[i]:i;
mx[i]=s[to[i]=k+1]-'a';
while(k){
k=nxt[k];
if(mx[i]<s[k+1]-'a')mx[i]=s[to[i]=k+1]-'a';
}
if(to[i]!=i+1)len=i-to[n=i]+1;
}
f[0][0]=1;
for(int i=1;i<=m;++i)
for(int j=0;j<=n;++j){
inc(f[i][to[j]],f[i-1][j]);
inc(f[i][0],(ll)(25-mx[j])*f[i-1][j]%mod);
}
for(int i=0;i<=n;++i)g[1][i]=25-mx[i];
for(int i=2;i<=m;++i)
for(int j=0;j<=n;++j)g[i][j]=g[i-1][to[j]];
int ans=!(m%len)?len:0;
for(int i=0;i<=m;++i)
for(int j=0;j<=n;++j)inc(ans,(ll)f[i][j]*g[m-i][j]%mod);
cout<<(pw-ans+mod)%mod<<endl;
return 0;
}