FFT

时间:2024-10-18 22:04:26
  void FFT(complex a[],int n,int fl){
for (int i=,j=n/;i<n;i++){
if (i<j) {complex t=a[i];a[i]=a[j];a[j]=t;};
int k;
for (k=(n>>);j&k;j^=k,k>>=);
j^=k;
} for (int i=;i<=n;i<<=){
complex w;w.r=cos(fl**pi/i);w.i=sin(fl**pi/i);
for (int j=;j<n;j+=i){
complex wi;wi.r=;wi.i=;
for (int k=j;k<j+i/;k++){
complex u=a[k],v=a[k+i/]*wi;
a[k]=u+v;a[k+i/]=u-v;
wi=wi*w;
}
}
} if (fl==-) for (int i=;i<n;i++) a[i].r/=n;
}

fl==1求点值 fl==-1插值

_________________________
DFT

void DFT(){
for (int i=;i<n;i++){
cp t=(cp){cos(*pi/n*i),sin(*pi/n*i)},bas=(cp){,};
for (int j=;j<n;j++){
tmp[i]=tmp[i]+bas*a[j];
bas=bas*t;
}
}
for (int i=;i<n;i++) a[i]=tmp[i];
} void IDFT(){
for (int i=;i<n;i++) P[i].r=P[i].i=;
for (int i=;i<n;i++){
cp t=(cp){cos(-*pi/n*i),sin(-*pi/n*i)},bas=(cp){,};
for (int j=;j<n;j++){
P[i]=P[i]+tmp[j]*bas;
bas=bas*t;
}
} for (int i=;i<n;i++) P[i].r=(int)(P[i].r/n+0.5);
}

-------------------------------------------------------------------------

CODECHEF JUNE15 MOREFB

系数为多项式的分治FFT

#include <bits/stdc++.h>
#define LL long long
#define LDB long double
using namespace std; const LDB pi=acos(-);
const LL mo=; int a[],n,k; struct data{
LL a_1,a_n;
}; inline data operator*(data a,data b) {return((data){(a.a_n*b.a_n+a.a_1*b.a_1)%mo,(a.a_n*b.a_n+a.a_1*b.a_n+a.a_n*b.a_1)%mo});}; struct cp{
LDB r_1,r_n,r_n2,i_1,i_n,i_n2; void set0(){
r_1=r_n=r_n2=i_1=i_n=i_n2=;
} void set(data a){
set0();
r_1=a.a_1;r_n=a.a_n;
}
}A[],B[]; inline cp operator *(cp a,cp b){
return((cp)
{
a.r_1*b.r_1-a.i_1*b.i_1,
a.r_n*b.r_1+a.r_1*b.r_n-a.i_n*b.i_1-a.i_1*b.i_n,
a.r_n2*b.r_1+a.r_n*b.r_n+a.r_1*b.r_n2-a.i_n2*b.i_1-a.i_n*b.i_n-a.i_1*b.i_n2,
a.r_1*b.i_1+a.i_1*b.r_1,
a.r_n*b.i_1+a.r_1*b.i_n+a.i_n*b.r_1+a.i_1*b.r_n,
a.r_n2*b.i_1+a.r_n*b.i_n+a.r_1*b.i_n2+a.i_n2*b.r_1+a.i_n*b.r_n+a.i_1*b.r_n2
});
} inline cp operator +(cp a,cp b){
return((cp)
{
a.r_1+b.r_1,
a.r_n+b.r_n,
a.r_n2+b.r_n2,
a.i_1+b.i_1,
a.i_n+b.i_n,
a.i_n2+b.i_n2,
});
} inline cp operator -(cp a,cp b){
return((cp)
{
a.r_1-b.r_1,
a.r_n-b.r_n,
a.r_n2-b.r_n2,
a.i_1-b.i_1,
a.i_n-b.i_n,
a.i_n2-b.i_n2,
});
} data getkth(int po){
data ret;ret.a_1=;ret.a_n=;
data bas;bas.a_1=;bas.a_n=;
for (;po;bas=bas*bas){
if (po&) ret=ret*bas;
po>>=;
}
return(ret);
} void FFT(cp a[],int n,int fl){
for (int i=,j=n/;i<n;i++){
if (i<j) {cp t=a[i];a[i]=a[j];a[j]=t;};
int k;
for (k=(n>>);j&k;j^=k,k>>=);
j^=k;
} for (int i=;i<=n;i<<=){
cp w;w.set0();
w.r_1=cos(fl**pi/i);w.i_1=sin(fl**pi/i);
for (int j=;j<n;j+=i){
cp wi;wi.set0();
wi.r_1=;wi.i_1=;
for (int k=j;k<j+i/;k++){
cp u=a[k],v=a[k+i/]*wi;
a[k]=u+v;a[k+i/]=u-v;
wi=wi*w;
}
}
} if (fl==-) for (int i=;i<n;i++) a[i].r_n2/=n,a[i].r_n/=n,a[i].r_1/=n;
}
vector <data> MUL(vector <data> &a,vector <data> &b){
int n=;
while (n<a.size()+b.size()) n<<=;
for (int i=;i<n;i++){
if (i<a.size()) A[i].set(a[i]);else A[i].set0();
if (i<b.size()) B[i].set(b[i]);else B[i].set0();
} FFT(A,n,);FFT(B,n,);
for (int i=;i<n;i++) A[i]=A[i]*B[i];
FFT(A,n,-); vector <data> ret;ret.resize(a.size()+b.size());
for (int i=;i<a.size()+b.size();i++){
LL tn2=(A[i].r_n2+0.5),tn=(A[i].r_n+0.5),t1=(A[i].r_1+0.5);
ret[i].a_n=(tn2+tn)%mo;ret[i].a_1=(tn2+t1)%mo;
}
return(ret);
} void show(vector <data> tmp1,vector <data> tmp2){
for (int i=;i<tmp1.size();i++) printf("%lld %lld|",tmp1[i].a_n,tmp1[i].a_1);printf("\n");
for (int i=;i<tmp2.size();i++) printf("%lld %lld|",tmp2[i].a_n,tmp2[i].a_1);printf("\n");
vector <data> res=MUL(tmp1,tmp2);
for (int i=;i<res.size();i++) printf("%lld %lld|",res[i].a_n,res[i].a_1);printf("\n\n");
} vector <data> solve(int l,int r){
if (l==r){
vector <data> ret;ret.resize();
ret[].a_1=;ret[].a_n=;
ret[]=getkth(a[l]);
return(ret);
} int mid=(l+r)>>;
vector <data> tmp1=solve(l,mid);
vector <data> tmp2=solve(mid+,r);
// show(tmp1,tmp2);
return(MUL(tmp1,tmp2));
} int main(){
scanf("%d%d",&n,&k);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
vector <data> ans=solve(,n);
printf("%lld\n",ans[k].a_n%mo);
}