LGP4199题解
因为没有简化题意一直没去做，直到今天讲这道题才口胡出来
要求对称，很明显这样一个“子序列”的对称中心只可能有一个，那么先枚举这个对称中心。
然后我们需要判断两个位置是否相同。看上去好像很困难。
考虑设计哈希函数 \(f(x,y)\)，使得 \(f(V_a,V_b)\neq 0\) 且 \(f(V_a,V_a)=f(V_b,V_b)=0\)。
首先等于 \(0\)，那么一定有一个 \((x-y)\)。其次，注意到字符集只有 \(2\)，为了方便，我们令 \(f(x,y)=-f(y,x)\)。那么就包含了 \((x-y)^2\)。
所以 \(f(x,y)=(V_x-V_y)^2=V_x^2+V_y^2-2V_xV_y\)，这就够了。
我们需要计算的是 \(match[i]=\sum_{j=0}f(i-j,i+j)\)，这有点像卷积。
拆开得到：
\[\sum_{j=0}(V_{i-j}^2+V_{i+j}^2)-2V_{i+j}V_{i-j} \]后面这玩意儿可以用前缀和搞定，前面这玩意儿做一个卷积就好啦。
这样做会算上连续的一段，使用 manacher 计算出来并且减掉就好啦。
复杂度 \(O(n\log n)\)。
#include
#include
typedef unsigned ui;
const ui M=1e5+5,G=3,mod=998244353,MOD=1e9+7;
ui n,V[M],S[M],pw2[M],f[M<<2];ui ans;char s[M];
ui p[M<<1];char c[M<<1];
inline ui min(const ui&a,const ui&b){
return a>b?b:a;
}
inline ui pow(ui a,ui b=mod-2){
ui ans(1);for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;return ans;
}
inline ui Add(const ui&a,const ui&b){
return a+b>=mod?a+b-mod:a+b;
}
inline ui Del(const ui&a,const ui&b){
return b>a?a-b+mod:a-b;
}
inline void swap(ui&a,ui&b){
ui c=a;a=b;b=c;
}
inline void DFT(ui*f,const ui&n){
for(ui len=n>>1;len>=1;len>>=1){
const ui w1=pow(G,(mod-1>>1)/len);
for(ui k=0;k>1)/len);
for(ui k=0;kR)mid=i,R=i+p[i]-1;
ans=(ans+(p[i]>>1))%MOD;
}
return ans;
}
signed main(){
scanf("%s",s+1);n=strlen(s+1);pw2[0]=1;
for(ui i=1;i<=n;++i){
V[i]=s[i]=='a'?1:2;pw2[i]=pw2[i-1]*2%MOD;
f[i]=V[i];S[i]=S[i-1]+V[i]*V[i];
}
ui len(1);
while(len