深圳制作网站制作公司,秦皇岛建筑,淘宝官网首页入口,资产管理公司网站建设方案快速傅里叶变化有不同的应用场景#xff0c;hdu4609就比较有意思。题目要求是给n个线段#xff0c;随机从中选取三个#xff0c;组成三角形的概率。 初始实在没发现这个怎么和FFT联系起来#xff0c;后来看了下别人的题解才突然想起来#xff1a;组合计数问题可以用多项式…快速傅里叶变化有不同的应用场景hdu4609就比较有意思。题目要求是给n个线段随机从中选取三个组成三角形的概率。 初始实在没发现这个怎么和FFT联系起来后来看了下别人的题解才突然想起来组合计数问题可以用多项式的卷积来解决。于是将给的数据进行卷积相乘利用FFT即可求出三角形任意两条线段组合的可能数目。 然后遍历初始数据将其作为最长边这里一开始也没想明白其实就是只要最长边大于短边之和其他两个不等式也自然可以满足。那么理论上说比它长的所有两边组合可能都可以。当然在这里要考虑三种特殊情况即在两边组合数目中减去这些情况 1.这两个边有可能一个边比最长边长一个边小于最长边 2.其中一个边就是要选的这个边 3.两个边其实都比最长边长这种情况要除以二 PS:G使用的是longlong类型C是_int64好久没写忘记了。 longlong在代码中间乘的运算也要加上否则还是会出错。 #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 real0.0,double image0.0) { rreal; iimage; } //以下为三种虚数运算的定义 complex operator(const complex o) { return complex(ro.r,io.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.ii*o.r); }
}x1[MAXN];void bitrev(complex *y,int l) //二进制平摊反转置换 O(logn)
{ register int i,j,k; for(i1,jl/2;il-1;i) { if(ij) swap(y[i],y[j]); //交换互为下标反转的元素 //ij保证只交换一次 kl/2; while(jk) //由最高位检索遇1变0遇0变1跳出 { j-k; k/2; } if(jk) jk; }
}
void fft(complex *in,int n,int flag)
{int i,j,k;complex u,t;bitrev(in,n);for(int i2;in;ii*2){complex wn(cos((2*PI*flag)/i),sin((2*PI*flag)/i));//初始化单位复根for(j0;jn;jji){complex w(1,0);for(kj;kji/2;k){uin[k];tw*in[ki/2];in[k]ut;in[ki/2]u-t;ww*wn;}}}if(flag-1)for(int i0;in;i)in[i].rin[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 j0;jn;j){scanf(%d,a[j]);num[a[j]];}sort(a,an);for(i 0;i a[n-1];i){x1[i].rnum[i];x1[i].i0;}int expandn1;while(expandn2*(a[n-1]1))expandnexpandn*2;for(i a[n-1]1;iexpandn;i){x1[i].r0;x1[i].i0;}fft(x1,expandn,1);for(i0;iexpandn;i)x1[i]x1[i]*x1[i];fft(x1,expandn,-1);for(i0;iexpandn;i){res[i](long long)(x1[i].r0.5);}//去除本身for(i0;in;i)res[a[i]a[i]]--;//变为组合for(i0;iexpandn;i)res[i]res[i]/2;//求出两边之和为i的所有可能//expandn(a[n-1]1)*2;sum[0]res[0];for(i1;iexpandn;i)sum[i]res[i]sum[i-1];long long ans0;for(i0;in;i){anssum[expandn-1]-sum[a[i]];//比长度为a[i]大的所有可能//去除一个大于a[i],一个小于a[i]ansans-(long long)(n-1-i)*i;//去除一个取自己ansans-(n-1);//去除取两个都大ansans-(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 转载于:https://www.cnblogs.com/holyprince/p/3596861.html
