裸的回文自动机回退。
对于一个长度为 $len$ 的回文串,在 $s$ 中出现一次的权值为 $(N-len+1)\cdot26^{N-len}$ 。
对于每个节点记录 $sum_p$ 表示 $p$ 在 $fail$ 树上所有祖先的权值和,如果插入一个字符后停在了 $p$ ,那么就会获得 $sum_p$ 的权值。
为了防止暴力回退复杂度爆炸,需要记录转移数组。
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=500000,maxt=1000000,maxi=26,MOD=1e9+7;
int te,N,m,n,pw[maxn+5];char s[maxt+5];
int pl,pb,son[maxt+5][maxi],qui[maxt+5][maxi],len[maxt+5],fai[maxt+5];
int sum[maxt+5],pos[maxt+5],si[maxt+5],who[maxt+5],ans;
#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
T tot=0;char ch=readc(),lst='+';
while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
char getlwr() {char ch=readc();while (!islower(ch)) ch=readc();return ch;}
int reads(char *s){
int len=0;char ch=getlwr();
while (islower(ch)) s[++len]=ch,ch=readc();
s[len+1]=0;return len;
}
struct fastO{
int si;char buf[100000];
fastO() {si=0;}
inline void putc(char ch){
if (si==100000) fwrite(buf,1,si,stdout),si=0;
buf[si++]=ch;
}
~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
static int len=0,buf[100];
if (x<0) putchar('-'),x=-x;
do buf[len++]=x%10,x/=10; while (x);
while (len) fo.putc(buf[--len]+48);
fo.putc(ch);
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
inline int newnode() {pl++;for (int i=0;i<maxi;i++) son[pl][i]=qui[pl][i]=0;return pl;}
inline int val(int p) {return len[p]<=N?MUL(N-len[p]+1,pw[N-len[p]]):0;}
void Extend(int i){
int c=s[i]-'a';if (i-len[pb]-1<1 || s[i-len[pb]-1]-'a'!=c) pb=qui[pb][c];
who[i]=pb;
if (!son[pb][c]){
int u=newnode(),k=fai[pb];len[u]=len[pb]+2;
if (s[i-len[k]-1]-'a'!=c) k=qui[k][c];k=son[k][c];
for (int i=0;i<maxi;i++) qui[u][i]=qui[k][i];
qui[u][s[i-len[k]]-'a']=k;fai[u]=k;son[pb][c]=u;
sum[u]=ADD(sum[fai[u]],val(u));
}
pb=son[pb][c];ans=ADD(ans,sum[pb]);
pos[i]=pb;si[i]=pl;
}
int main(){
pw[0]=1;for (int i=1;i<=maxn;i++) pw[i]=MUL(pw[i-1],26);
for (readi(te);te;te--){
readi(N);readi(m);n=reads(s);
pl=-1;newnode();newnode();
fai[0]=fai[1]=1;len[0]=0;len[1]=-1;sum[0]=sum[1]=0;
for (int i=0;i<maxi;i++) qui[0][i]=1;
pb=0;pos[0]=pb;si[0]=pl;
ans=0;for (int i=1;i<=n;i++) Extend(i);
writei(ans);
for (int t=1,tp;t<=m;t++){
readi(tp);
if (tp==2){
ans=ADD(ans,MOD-sum[pos[n]]);
if (si[n]>si[n-1]) son[who[n]][s[n]-'a']=0;
n--;pb=pos[n];pl=si[n];
} else s[++n]=getlwr(),Extend(n);
writei(ans);
}
}
return 0;
}