首页 > 代码库 > FFT

FFT

2024-08-14 00:19:48   221人阅读

简短几句话说说FFT....

多项式可用系数和点值表示，n个点可确定一个次数小于n的多项式。

多项式乘积为 f(x)*g(x)，点值下O(n)可求得多项式乘积的点值表示。

我们所需要的就是快速地将两个系数多项式表示成点值多项式，O(n)求得乘积的点值表示后还原成系数多项式。

这里就需要套FFT板子了...

FFT中取n个单位根，需要n是2的幂。

又因为n个点可确定一个次数小于n的多项式，所以n > 乘积多项式的最高次数。

以上。

HDU4609 n个木棍任取三根能组成三角形的概率。

数组开小莫名T,WA.

技术分享
 1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int N = 4e5+10; 5 struct comp{ 6     double r,i;comp(double _r=0,double _i=0){r=_r;i=_i;} 7     comp operator+(const comp x){return comp(r+x.r,i+x.i);} 8     comp operator-(const comp x){return comp(r-x.r,i-x.i);} 9     comp operator*(const comp x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}10 };11 const double pi=acos(-1.0);12 void FFT(comp a[],int n,int t){13     for(int i=1,j=0;i<n-1;i++){14         for(int s=n;j^=s>>=1,~j&s;);15             if(i<j)swap(a[i],a[j]);16     }17     for(int d=0;(1<<d)<n;d++){18         int m=1<<d,m2=m<<1;19         double o=pi/m*t;comp _w(cos(o),sin(o));20         for(int i=0;i<n;i+=m2){21             comp w(1,0);22             for(int j=0;j<m;j++){23                 comp &A=a[i+j+m],&B=a[i+j],t=w*A;24                 A=B-t;B=B+t;w=w*_w;25             }26         }27     }28     if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;29 }30 comp x[N];31 ll num[N], sum[N];32 int main(){33     int T; scanf("%d", &T);34     while(T--){35         memset(num, 0, sizeof num);36         int n, u, maxnum = -1; scanf("%d", &n);37         for(int i = 0; i < n; i++){38             scanf("%d", &u);39             maxnum = max(maxnum, u), num[u]++;40         }41         int len = 1;42         while(len <= maxnum*2) len <<= 1;43         for(int i = 0; i < len; i++)44             x[i] = comp(num[i], 0);45         FFT(x, len, 1);46         for(int i = 0; i < len; i++)47             x[i] = x[i]*x[i];48         FFT(x, len , -1);49         for(int i = 0; i < len; i++)50             sum[i] = x[i].r+0.5;51         for(int i = 0; i < len; i+=2)52             sum[i] -= num[i>>1];//去掉两次取的木棍相同的53         for(int i = 0; i < len; i ++)54             sum[i] >>= 1;//算了2次55         for(int i = 1; i < len; i++)56             sum[i] += sum[i-1];57         ll tot = (ll)n*(n-1)*(n-2)/6, ans = tot;58         for(int i = 0; i <= maxnum; i++)59                 ans -= num[i]*sum[i];//去掉不能组成三角形的60         printf("%.7f\n", 1.0*ans/tot);61     }62     return 0;63 }
View Code

 

FFT


联系
我们