题目
题目描述
对于一个字符串$\vert S\vert$，我们定义fail[i]，表示最大的x使得S[1..x]=S[i-x+1..i]，满足$x<i$
显然对于一个字符串，如果我们将每个$0\le i\le\vert S\vert$看成一个结点，除了i=0以外i向fail[i]连边，这是一颗树的形状，根是0
我们定义这棵树是$G(S)$，设$f(S)$是$G(S)$中除了0号点以外所有点的深度之和，其中0号点的深度为-1 定义$key(S)$等于$S$的所有非空子串$S’$的$f(S’)$之和
给定一个字符串$S$，现在你要实现以下几种操作：
1.在$S$最后面加一个字符
2.询问$key(S)$
善良的出题人不希望你的答案比long long大，所以你需要将答案对1e9+7取模
输入
第一行一个正整数Q
Q<=10^5
第二行一个长度为Q的字符串$S$
输出
输出Q行，第i行表示前i个字符组成的字符串的答案
输入样例
5
abaab
输出样例
0
0
1
4
9
题解
神仙题
发现一个字符串的$f$就是ta所有前缀出现次数$-1$的和，这个可以手玩一下得出
要求的答案$\sum_{S’\in S}f(S’)$，考虑$S’$在哪些子串中作前缀
$SAM$中，某个状态$i$的$right$集合${pos_1,pos_2,…,pos_n}$大小是$n$，那么$pos_j$产生的贡献就是$(Q-pos_j+1)\times (j-1)\times (lenmax_i-lenmin_i+1)$（与前面每个$pos$组合）
好像很难直接计算？
考虑一下加点过程，加入一个点的时候，某些状态的$right$不变，某些状态的$right$大小会$+1$，对于$right$不变的（用集合$A$表示），答案会增加$\sum_{i\in A} \tbinom{right_i}{2}\times (lenmax_i-lenmin_i+1)$；对于$right+1$的（用集合$B$表示），答案会增加$(\sum_{i\in B}\tbinom{right_i+1}{2}+\sum_{i\in B}right_i)\times (lenmax_i-lenmin_i+1)$
因为每次$right+1$的集合肯定是节点$1$到某个节点的路径，发现只用维护修改树链和查询树链，用树链剖分即可（累加累加累加……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=2e5+5,mod=1e9+7;
int n;
char a[MAX];
struct SAM{
struct p{
int x,y;
}c[MAX];
struct q{
int x,_val,tag;
}s[MAX<<2];
int l,r,L,cnt,num;
int h[MAX],len[MAX],re[MAX],ID[MAX],fa[MAX],id[MAX],top[MAX],val[MAX],siz[MAX],_son[MAX];
int son[MAX][26];
SAM() {l=r=1;}
void ins(int x)
{
int tt=r;
len[r=++l]=++L,ID[L]=l;
for(;tt&&!son[tt][x];tt=fa[tt])
son[tt][x]=r;
if(!tt) return void(fa[r]=1);
int qwq=son[tt][x];
if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l;
for(int i=0;i<26;++i)
son[l][i]=son[qwq][i];
for(int i=tt;son[i][x]==qwq;i=fa[i])
son[i][x]=l;
}
void add(int x,int y) {c[++num]=(p){h[x],y},h[x]=num;}
void dfs(int x=1)
{
val[x]=len[x]-len[fa[x]],siz[x]=1;
for(int i=h[x];i;i=c[i].x)
{
dfs(c[i].y),siz[x]+=siz[c[i].y];
if(siz[c[i].y]>siz[_son[x]]) _son[x]=c[i].y;
}
}
void dfs1(int x=1,int tp=1)
{
top[x]=tp,re[id[x]=++cnt]=x;
if(!_son[x]) return;
dfs1(_son[x],tp);
for(int i=h[x];i;i=c[i].x)
if(c[i].y^_son[x]) dfs1(c[i].y,c[i].y);
}
void down(int k)
{
if(s[k].tag)
{
int F=s[k].tag;
s[k].tag=0,s[tl].x=(s[tl].x+1ll*s[tl]._val*F%mod)%mod,s[tr].x=(s[tr].x+1ll*s[tr]._val*F%mod)%mod,s[tl].tag+=F,s[tr].tag+=F;
}
}
void pus(int k) {s[k].x=(s[tl].x+s[tr].x)%mod,s[k]._val=(s[tl]._val+s[tr]._val)%mod;}
void build(int l,int r,int k)
{
if(l==r) return void(s[k]._val=val[re[l]]);
build(l,mid,tl),build(mid+1,r,tr),pus(k);
}
int ask(int l,int r,int k,int L,int R)
{
if(l>R||L>r) return 0;
int ans;
if(l>=L&&r<=R) return ans=s[k].x,s[k].x=(s[k].x+s[k]._val)%mod,++s[k].tag,ans;
down(k),ans=(ask(l,mid,tl,L,R)+ask(mid+1,r,tr,L,R))%mod;
return pus(k),ans;
}
void Init()
{
for(int i=2;i<=l;++i)
add(fa[i],i);
dfs(),dfs1(),build(1,l,1);
}
int ASK(int x)
{
int ans=0;
while(top[x]^1) ans=(ans+ask(1,l,1,id[top[x]],id[x]))%mod,x=fa[top[x]];
return (ans+(id[x]>=2?ask(1,l,1,2,id[x]):0))%mod;
}
void Solve()
{
Init();
for(int i=1,tot=0,ans=0;i<=n;++i)
tot=(tot+ASK(ID[i]))%mod,printf("%d\n",(ans+=tot)%=mod);
}
}_S;
int main()
{
scanf("%d%s",&n,a+1);
for(int i=1;i<=n;++i)
_S.ins(a[i]-'a');
return _S.Solve(),0;
}
