注意：下述的 \(s[a... b]\) 均表示字符串 \(s\) 中位置 \(a\) 到位置 \(b\) 构成的子串，位置均从 \(1\) 开始编号。
我们递归定义一个长度为 \(n\) 的字符串 \(s\) 的关键词个数如下：
- 对于一个空字符串，其关键词个数为 \(-1\) .
- 对于字符串 \(s\)，若 \(s[1...x]=s[n-x+1...n]\) 且 \(1\leq x<n\)，则称 \(x\) 是一个”强调位置“。在字符串中找到最靠后的强调位置 \(t\) ，\(s\) 的关键词\(s[1...t]\)个数为构成的关键词个数 \(+1\) .
同时，我们定义其美观程度为 \(\sum\limits_{i=1}^nword(s[1...i])\)，即每个前缀的关键词个数之和。现在给定一条长度为的语录，用一个只包含小写字符，长度恰好为的字符串来表示。位置的字符为第个时刻说出的。也就是说，在第个时刻后，目前说出的语录是，即的一个前缀。
对于每个时刻，你需要统计目前说出的语录的所有连续子串的美观程度之和。由于答案可能过大，你需要对\(10^9+7\) 取模。
\(1\leq n\leq 10^5\)
考虑 \(\sum\limits_{i=1}^n word(s[1...i])\) ，其实就是每一个时刻，设每个串 \(s\) 的出现次数 \(num\)，那么 \(\sum\limits_{i=1}^n word(s[1...i])=\sum\dbinom{cnt}{2}\) .
想到这里就已经成功了很多，考虑用 sam 和线段树实现 .
这个线段树要支持树剖 .
时间复杂度 : \(O(n\log^2 n)\)
空间复杂度 : \(O(n)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
int res=0;
while(ch>='0'&&ch<='9'){
res=res*10+ch-'0';
ch=getchar();
}
return res;
}
inline void print(int res){
if(res==0){
putchar('0');
return;
}
int a[10],len=0;
while(res>0){
a[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)
putchar(a[i]+'0');
}
class state{
public:
int len,link;
map<char,int>nxt;
};
state st[100010<<1];
int sz=0,lst;
void sam_init(){
st[0].len=0;
st[0].link=-1;
sz++;
lst=0;
}
int pos[100010],cnt=0;
void sam_extend(char c){
int cur=sz++;
st[cur].len=st[lst].len+1;
int p=lst;
while(p!=-1&&!st[p].nxt.count(c)){
st[p].nxt[c]=cur;
p=st[p].link;
}
if(p==-1){
st[cur].link=0;
}else{
int q=st[p].nxt[c];
if(st[p].len+1==st[q].len){
st[cur].link=q;
}else{
int clone=sz++;
st[clone].len=st[p].len+1;
st[clone].nxt=st[q].nxt;
st[clone].link=st[q].link;
while(p!=-1&&st[p].nxt[c]==q){
st[p].nxt[c]=clone;
p=st[p].link;
}
st[q].link=st[cur].link=clone;
}
}
pos[cnt++]=cur;
lst=cur;
}
const int mod=1e9+7;
inline void upd(int &x,int y){x=(x+y)%mod;}
class node{public:int len,val1,val2,tag;}t[200010<<2];
int rid[200010],id[200010];
void build(int x,int l,int r){
if(l==r){
if(l!=0){
t[x]=(node){st[rid[l]].len-st[st[rid[l]].link].len,0,0,0};
}
else t[x]=(node){0,0,0,0};
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
t[x]=(node){t[x<<1].len+t[x<<1|1].len,0,0,0};
}
void pd(int x){
if(t[x].tag==0)return;
upd(t[x<<1].val2,1ll*t[x].tag*t[x].tag%mod*t[x<<1].len%mod);
upd(t[x<<1].val2,2ll*t[x].tag*t[x<<1].val1%mod);
upd(t[x<<1].val1,1ll*t[x].tag*t[x<<1].len%mod);
upd(t[x<<1].tag,t[x].tag);
upd(t[x<<1|1].val2,1ll*t[x].tag*t[x].tag%mod*t[x<<1|1].len%mod);
upd(t[x<<1|1].val2,2ll*t[x].tag*t[x<<1|1].val1%mod);
upd(t[x<<1|1].val1,1ll*t[x].tag*t[x<<1|1].len%mod);
upd(t[x<<1|1].tag,t[x].tag);
t[x].tag=0;
}
void pu(int x){
t[x].val1=(t[x<<1].val1+t[x<<1|1].val1)%mod;
t[x].val2=(t[x<<1].val2+t[x<<1|1].val2)%mod;
}
void upd(int x,int l,int r,int cl,int cr){
if(l==cl&&r==cr){
if(l!=r)pd(x);
upd(t[x].tag,1);
upd(t[x].val2,(t[x].len+2*t[x].val1)%mod);
upd(t[x].val1,t[x].len);
return;
}
pd(x);
int mid=(l+r)>>1;
if(cl<=mid)upd(x<<1,l,mid,cl,min(cr,mid));
if(mid+1<=cr)upd(x<<1|1,mid+1,r,max(cl,mid+1),cr);
pu(x);
}
int n;
string s;
vector<int>g[200010];
int sum[200010],heavy[200010];
void get_heavy(int x,int fa){
heavy[x]=-1;
sum[x]=1;
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i];
if(to==fa)continue;
get_heavy(to,x);
sum[x]+=sum[to];
if(heavy[x]==-1||sum[heavy[x]]<sum[to])heavy[x]=to;
}
}
int p[200010];
int head[200010];
void dfs(int x,int fa){
rid[cnt]=x;
id[x]=cnt++;
p[x]=fa;
if(heavy[x]!=-1){
head[heavy[x]]=head[x];
dfs(heavy[x],x);
}
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i];
if(to==fa||to==heavy[x])continue;
head[to]=to;
dfs(to,x);
}
}
inline void add(int x){
while(head[x]!=0){
upd(1,0,sz-1,id[head[x]],id[x]);
x=p[head[x]];
}
if(x!=0){
upd(1,0,sz-1,1,id[x]);
}
}
inline int ksm(int x,int k){
if(k==0)return 1;
int res=ksm(x,k>>1);
res=1ll*res*res%mod;
if(k&1)res=1ll*res*x%mod;
return res;
}
int main(){
freopen("keyword.in","r",stdin);
freopen("keyword.out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>s;
sam_init();
for(int i=0;i<(int)s.size();i++)sam_extend(s[i]);
for(int i=1;i<sz;i++){
g[st[i].link].push_back(i);
}
memset(heavy,-1,sizeof(heavy));
get_heavy(0,-1);
cnt=0;
dfs(0,-1);
build(1,0,cnt-1);
int ans=0;
for(int i=0;i<n;i++){
add(pos[i]);
ans=(ans+1ll*(t[1].val2-t[1].val1+mod)%mod*ksm(2,mod-2)%mod)%mod;
print(ans);
putchar(' ');
}
putchar('\n');
return 0;
}
/*inline? ll or int? size? min max?*/
/*
6
ababab
*/