wa0求助
查看原帖
wa0求助
749665
huta0楼主2024/5/7 06:20
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define ai_jiang signed main()
#define a_all a.begin(),a.end()
using namespace std;
typedef long long ll;
struct complex { 
     double x,y;
     complex() {}
     complex(double a,double b) { x=a,y=b;}
};
complex operator+(complex a,complex b) { return {a.x+b.x,a.y+b.y}; }
complex operator-(complex a,complex b) { return {a.x-b.x,a.y-b.y}; }
complex operator*(complex a,complex b) { return {a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x}; }
string s; int p;
const int mod = 1e9+7;
namespace ai {
     const double pi = acos(-1);
     const int N = 2e5+5;
     complex a[N<<2],b[N<<2];
     ll f[N<<2];
     void fft(complex *a,int n,int op) {
           if(n==1) return;
           complex a1[n>>1],a2[n>>1];
           rep(i,0,(n>>1)-1) a1[i]=a[i<<1],a2[i]=a[i<<1|1];
           fft(a1,n>>1,op), fft(a2,n>>1,op);
           complex w1(cos(2*pi/n),sin(2*pi/n)*op);
           complex wk(1,0);
           rep(i,0,(n>>1)-1) {
                 a[i]=a1[i]+a2[i]*wk;
                 a[i+(n>>1)]=a1[i]-a2[i]*wk; wk=wk*w1;
           }
     }
};
using namespace ai;
namespace tempest {
     int h[N<<2];
     ll pad=0,as=0;
     void init() {
           char st[N<<1]; int top=0;
           st[0]='~', st[++top]='@';
           for(char i:s) st[++top]=i,st[++top]='@';
           s=st; p=top;
     }
     void manacher() {
           int r=0,md=1;
           for(int i=1;i<s.size()-1;i++) {
                h[i]=i<=r?min(h[(md<<1)-i],r-i):1;
                while(s[i+h[i]]==s[i-h[i]]) ++h[i];
                if(i+h[i]>r) r=i+h[i],md=i;
                pad+=(h[i]>>1); pad%=mod;
           } pad%=mod;
     }
     ll pow(ll a,ll b) {
           ll base=a,ans=1;
           while(b) {
                 if(b&1) ans=ans*base%mod;
                 b>>=1; base=base*base%mod;
           } return ans;
     }
}
using namespace tempest;
ai_jiang {
    cin.tie(0);
    cout.tie(0);
    cin>>s; string k=s; init(); manacher(); int x = p;
    for(p=1;p<=x;p<<=1);
    rep(i,0,k.size()-1) a[i].x=(k[i]=='a');
    fft(a,p,1);
    rep(i,0,p-1) a[i]=a[i]*a[i];
    fft(a,p,-1);
    rep(i,0,p-1) f[i]=(f[i]%mod+(ll)(a[i].x/p+0.5)%mod)%mod;
    rep(i,0,k.size()-1) b[i].x=(k[i]=='b');
    fft(b,p,1);
    rep(i,0,p-1) b[i]=b[i]*b[i];
    fft(b,p,-1);
    rep(i,0,p-1) f[i]=(f[i]%mod+(ll)(b[i].x/p+0.5)%mod)%mod;
    
    rep(i,0,p-1) { as=as+pow(2,(f[i]+1)>>1)-1; as%=mod; }
    cout<<((as%mod-pad%mod)%mod+mod)%mod;
    
    return 0;
}
2024/5/7 06:20
加载中...