题目概述

有一个AB字符串，问间距为 $k$ 的BA对有多少，其中 $k\in[1,n-1]$ 。

解题报告

emm……应该算是生成函数吧？令A的位置的权值为下标，B的位置的权值为下标的相反数，那么只需要统计所有BA的权值加和，这个就是多项式乘法，用FFT快速得出。

BB和AB的权值加和都是负数，所以不用管，但会发现AA可能被算了，所以减掉。

示例程序

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef double DB;typedef pair<DB,DB> CN;
const int maxn=1000000,maxt=4194304;const DB pi=acos(-1);

int n,m,a[maxn+5],rev[maxt],ans[maxn+5];CN A[maxt],B[maxt];

inline CN operator + (const CN &a,const CN &b) {return mp(a.fr+b.fr,a.sc+b.sc);}
inline CN operator - (const CN &a,const CN &b) {return mp(a.fr-b.fr,a.sc-b.sc);}
inline CN operator * (const CN &a,const CN &b) {return mp(a.fr*b.fr-a.sc*b.sc,a.fr*b.sc+a.sc*b.fr);}
inline void Rev(int n,int len) {for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<len-1);}
inline void FFT(CN *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        CN w=mp(1,0),wn=mp(cos(pi/k),f*sin(pi/k)),x,y;
        for (int i=0;i<n;i+=k<<1,w=mp(1,0))
            for (int j=0;j<k;j++,w=w*wn)
                x=a[i+j],y=a[i+j+k]*w,a[i+j]=x+y,a[i+j+k]=x-y;
    }if (f<0) for (int i=0;i<n;i++) a[i].fr/=n;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (char ch=getchar();isupper(ch);ch=getchar()) n++,ch=='B'?a[n]=-n:a[n]=n;
    for (int i=1;i<=n;i++) A[a[i]+n].fr++;int len=0;for (m=1;m<=(n<<2);m<<=1) len++;Rev(m,len);
    FFT(A,m,1);for (int i=0;i<m;i++) B[i]=A[i]*A[i];FFT(B,m,-1);
    for (int i=1;i<n;i++) ans[i]=int(B[i+(n<<1)].fr+0.5);
    for (int i=0;i<m;i++) A[i]=mp(0,0);for (int i=1;i<=n;i++) if (a[i]>0) A[a[i]+n].fr++;
    FFT(A,m,1);for (int i=0;i<m;i++) B[i]=A[i]*A[i];FFT(B,m,-1);
    for (int i=1;i<n;i++) ans[i]=ans[i]-int(B[i+(n<<1)].fr+0.5)>>1,printf("%d\n",ans[i]);
}