BZOJ3160万径人踪灭-回文子序列（位置对称）计数

link：https://www.luogu.com.cn/problem/P4199
写manacher看到的（其实重点并不在manacher）
题意：给一个仅包含2种字母的字符串，问有多少种不同的子序列，满足：

• 内容和位置都是对称的
• 不能是连续的一段
  \(1\leq n\leq 10^5\)

答案=子序列个数-回文串个数，回文串用manacher跑，子序列则考虑回文中心，假设 \(f_i\) 表示位置 \(i\) 处是否是字符 a （用0或1表示），则 $$\sum_{i\leq k-i} f_i \times f_{k-i}$$ 即为仅包含 a 的回文中心为 \(\frac{k}{2}\) 的子序列的个数，设 \(F(x)=\sum f_i x^i\)，同样对字符 b 设一个 \(G(x)\)，注意中心恰好是某个字符的情况，则答案为：$$ \sum_{k=0}^{2n} 2^ {[x^k](\lceil F^2(x)/2\rceil +\lceil G^2(x)/2\rceil)}-1$$

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MOD2=1e9+7;
int ksm(int a,ll b,int MOD){
    int ret=1;a%=MOD;
    for(;b;b>>=1,a=(ll)a*a%MOD)if(b&1)ret=(ll)ret*a%MOD;
    return ret;
}
vector<int> manacher(string s) {
    string t="#";
    for(auto c:s)t+=c,t+='#';
    int n=t.size();
    vector<int> r(n);
    for(int i=0,j=0;i<n;i++){
        if(2*j-i>=0&&j+r[j]>i)r[i]=min(r[2*j-i],j+r[j]-i);
        while(i-r[i]>=0&&i+r[i]<n&&t[i-r[i]]==t[i+r[i]])r[i]++;
        if(i+r[i]>j+r[j])j=i;
    }
    return r;
}
namespace NTT{
    const int N=1<<20;
    const int MOD=998244353;
    int F[N],G[N],r[N],w[N];
    void ntt(int n,int *x,int opt){
        for(int i=0;i<n;i++)if(r[i]<i)swap(x[i],x[r[i]]);
        for(int i=1;i<n;i<<=1){
            int gn=ksm(opt==1?3:332748118,(MOD-1)/(i<<1),MOD);
            w[0]=1;
            for(int k=1;k<i;k++)w[k]=(ll)w[k-1]*gn%MOD;
            for(int j=0;j<n;j+=(i<<1))
                for(int k=0;k<i;k++){
                    int t1=x[j+k],t2=(ll)x[j+k+i]*w[k]%MOD;
                    x[j+k]=(t1+t2)%MOD;
                    x[j+k+i]=(t1-t2+MOD)%MOD;
                }
        }
        if(opt==-1){
            int inv=ksm(n,MOD-2,MOD);
            for(int i=0;i<n;i++)x[i]=1ll*x[i]*inv%MOD;
        }
    }
    int work(string s){
        int n=s.length();
        rep(i,0,n-1){
            if(s[i]=='a')F[i]=1;
            else G[i]=1;
        }
        int p=1,deg=n+n,ans=0;
        while(p<=deg)p<<=1;
        rep(i,0,p-1)r[i]=(i&1)*(p>>1)+(r[i>>1]>>1);
        ntt(p,F,1);ntt(p,G,1);
        rep(i,0,p-1)F[i]=(ll)F[i]*F[i]%MOD;
        rep(i,0,p-1)G[i]=(ll)G[i]*G[i]%MOD;
        ntt(p,F,-1);ntt(p,G,-1);
        
        rep(i,0,2*(n-1))F[i]=(F[i]+1)/2,G[i]=(G[i]+1)/2;
        rep(i,0,2*(n-1))ans=(ans+ksm(2,F[i]+G[i],MOD2)-1)%MOD2;
        return ans;
    }
}
int main(){
    fastio;
    string s;cin>>s;
    auto ans=NTT::work(s);
    auto r=manacher(s);
    for(auto x:r){
        if(x&1)ans=(ans+MOD2-(x-1)/2)%MOD2;
        else ans=(ans+MOD2-x/2)%MOD2;
    }
    cout<<ans;
    return 0;
}