本文共 1543 字，大约阅读时间需要 5 分钟。
题目大意:给你一个ab序列,问不连续回文子序列的个数.
FFT加上一些计数原理即可A掉此题,主要需要注意的是两字符间的位置也需要运算.
对FFT,感觉就是一个双重循环,不过这个双重循环内部运算必须是乘法,而且复杂度不错.
无聊的话,每个FFT的题基本上都可以写成双重循环的结构.
顺便学一下mancher.
#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL long long#define up(i,j,n) for(LL i=j;i<=n;i++)#define pii pair #define db double#define eps 1e-4#define FILE "dealing"LL read(){ LL x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0',ch=getchar();} return x*f;}const LL maxn=401000,inf=1000000000000000LL,limit=20000,mod=1000000007;bool cmin(LL& a,LL b){return a>b?a=b,true:false;}bool cmax(LL& a,LL b){return a mx){ mx=i+p[i]; id=i; } } LL ret=0; for(LL i=1;i >1; cp wn(cos(pi/l),f*sin(pi/l)); for(LL i=1;i >1]>>1)|((i&1)<<(H-1)); FFT(A,1);FFT(B,1); for(LL i=0;i >=1)if(b&1)ans=ans*a%mod;return ans;}LL f[maxn];int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); scanf("%s",s); n=strlen(s); up(i,0,n-1)ch[i]=s[i]; LL y=Mancher::solve(ch,n); up(i,0,n-1)a[i]=s[i]=='a'; up(i,0,n-1)b[i]=s[i]=='b'; FFT::solve(a,a,n,n,c); for(int i=0;i <<1;i++)f[i]+=c[i]; FFT::solve(b,b,n,n,c); for(int i=0;i <<1;i++)f[i]+=c[i]; LL ans=0; for(int i=0;i <<1;i++) ans=(ans+mul(2,(f[i]+1)/2)+mod-1)%mod; ans=(ans%mod-y+mod)%mod; printf("%lld\n",ans); return 0;}
转载于:https://www.cnblogs.com/chadinblog/p/6501239.html