代码

#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std;

const int N=3000010;
const double pi=acos(-1.);
char s1[N],s2[N];
int n,m,L,x,tmp[10],rev[N];
struct C{ double x,y; }a[N],b[N];

C operator +(const C &a,const C &b){ return (C){a.x+b.x,a.y+b.y}; }
C operator -(const C &a,const C &b){ return (C){a.x-b.x,a.y-b.y}; }
C operator *(const C &a,const C &b){ return (C){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x}; }

void FFT(C a[],int f){
    rep(i,0,n-1) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int i=1; i<n; i<<=1){
        C wn=(C){cos(pi/i),f*sin(pi/i)};
        for (int p=i<<1,j=0; j<n; j+=p){
            C w=(C){1,0};
            for (int k=0; k<i; k++,w=w*wn){
                C x=a[j+k],y=w*a[i+j+k]; a[j+k]=x+y; a[i+j+k]=x-y;
            }
        }
    }
}

void poly_multiply(unsigned *a1, int n, unsigned *b1, int m, unsigned *c){
    rep(i,0,n) a[i].x=a1[i];
    rep(i,0,m) b[i].x=b1[i];
    m=n+m; for (n=1; n<=m; n<<=1) L++;
    rep(i,0,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
    rep(i,0,n) a[i]=(C){a[i].x+b[i].x,a[i].x-b[i].x};
    FFT(a,1);
    rep(i,0,n-1) a[i]=a[i]*a[i];
    FFT(a,-1);
    rep(i,0,m) c[i]=a[i].x/n/4+0.5;
}

评测结果