快速傅里葉變化有不同的應(yīng)用場(chǎng)景，hdu4609就比較有意思。題目要求是給n個(gè)線段，隨機(jī)從中選取三個(gè)，組成三角形的概率。

初始實(shí)在沒發(fā)現(xiàn)這個(gè)怎么和FFT聯(lián)系起來，后來看了下別人的題解才突然想起來：組合計(jì)數(shù)問題可以用多項(xiàng)式的卷積來解決。于是將給的數(shù)據(jù)進(jìn)行卷積相乘，利用FFT即可求出三角形任意兩條線段組合的可能數(shù)目。

然后遍歷初始數(shù)據(jù)，將其作為最長(zhǎng)邊（這里一開始也沒想明白，其實(shí)就是只要最長(zhǎng)邊大于短邊之和，其他兩個(gè)不等式也自然可以滿足）。那么理論上說比它長(zhǎng)的所有兩邊組合可能都可以。當(dāng)然在這里要考慮三種特殊情況：（即在兩邊組合數(shù)目中減去這些情況）

1.這兩個(gè)邊有可能一個(gè)邊比最長(zhǎng)邊長(zhǎng)，一個(gè)邊小于最長(zhǎng)邊

2.其中一個(gè)邊就是要選的這個(gè)邊

3.兩個(gè)邊其實(shí)都比最長(zhǎng)邊長(zhǎng)，這種情況要除以二

?

PS:G++使用的是longlong類型，C++是_int64，好久沒寫忘記了。

longlong在代碼中間乘的運(yùn)算也要加上，否則還是會(huì)出錯(cuò)。

#include <iostream> #include <cmath> #include <algorithm> //spell! #include <string.h> #define MAXN 400040 #define PI acos(-1.0) using namespace std;struct complex { double r,i; complex(double real=0.0,double image=0.0) { r=real; i=image; } //以下為三種虛數(shù)運(yùn)算的定義 complex operator+(const complex o) { return complex(r+o.r,i+o.i); } complex operator-(const complex o) { return complex(r-o.r,i-o.i); } complex operator*(const complex o) { return complex(r*o.r-i*o.i,r*o.i+i*o.r); } }x1[MAXN];void bitrev(complex *y,int l) //二進(jìn)制平攤反轉(zhuǎn)置換 O(logn) { register int i,j,k; for(i=1,j=l/2;i<l-1;i++) { if(i<j) swap(y[i],y[j]); //交換互為下標(biāo)反轉(zhuǎn)的元素 //i<j保證只交換一次 k=l/2; while(j>=k) //由最高位檢索，遇1變0，遇0變1，跳出 { j-=k; k/=2; } if(j<k) j+=k; } } void fft(complex *in,int n,int flag) {int i,j,k;complex u,t;bitrev(in,n);for(int i=2;i<=n;i=i*2){complex wn(cos((2*PI*flag)/i),sin((2*PI*flag)/i));//初始化單位復(fù)根for(j=0;j<n;j=j+i){complex w(1,0);for(k=j;k<j+i/2;k++){u=in[k];t=w*in[k+i/2];in[k]=u+t;in[k+i/2]=u-t;w=w*wn;}}}if(flag==-1)for(int i=0;i<n;i++)in[i].r=in[i].r/n; }int a[100003]; long long res[MAXN]; long long sum[MAXN]; long long num[MAXN]; int main() {int T;scanf("%d",&T);while(T--){int n,i;scanf("%d",&n);memset(res,0,sizeof(res));memset(sum,0,sizeof(sum));memset(num,0,sizeof(num));for(int j=0;j<n;j++){scanf("%d",&a[j]);num[a[j]]++;}sort(a,a+n);for(i = 0;i <=a[n-1];i++){x1[i].r=num[i];x1[i].i=0;}int expandn=1;while(expandn<2*(a[n-1]+1))expandn=expandn*2;for(i = a[n-1]+1;i<expandn;i++){x1[i].r=0;x1[i].i=0;}fft(x1,expandn,1);for(i=0;i<expandn;i++)x1[i]=x1[i]*x1[i];fft(x1,expandn,-1);for(i=0;i<expandn;i++){res[i]=(long long)(x1[i].r+0.5);}//去除本身for(i=0;i<n;i++)res[a[i]+a[i]]--;//變?yōu)榻M合for(i=0;i<expandn;i++)res[i]=res[i]/2;//求出兩邊之和為i的所有可能//expandn=(a[n-1]+1)*2;sum[0]=res[0];for(i=1;i<expandn;i++)sum[i]=res[i]+sum[i-1];long long ans=0;for(i=0;i<n;i++){ans+=sum[expandn-1]-sum[a[i]];//比長(zhǎng)度為a[i]大的所有可能//去除一個(gè)大于a[i],一個(gè)小于a[i]ans=ans-(long long)(n-1-i)*i;//去除一個(gè)取自己ans=ans-(n-1);//去除取兩個(gè)都大ans=ans-(long long)(n-1-i)*(n-2-i)/2;}long long all = (long long)n*(n-1)*(n-2)/6;printf("%.7lf\n",(double)ans/all);} } hdu 4609

?

轉(zhuǎn)載于:https://www.cnblogs.com/holyprince/p/3596861.html

總結(jié)

以上是生活随笔為你收集整理的快速傅里叶变换应用之二 hdu 4609 3-idiots的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。