HDU 4609 3-idiots-白红宇

HDU 4609 3-idiots

阅读量：6813 次

发布时间：2019-06-26

本文共 1100 字，大约阅读时间需要 3 分钟。

问给定n条小木棍随机选3根构成三角形的概率

看起来和多项式没啥关系对不对 = =

但实际上它的确可以用多项式来做qaq

我们构造多项式 $f(x)=\sum x^{a_i}$

然后自乘一下就能得到两根木棍拼起来的方案数

然后枚举所有拼出来的长度算一下>=这个长度的木棍个数

求出不能拼成三角形的方案数

然后最后用 C(3,n) 减一减除一除就可以了qwq

【注意sum的预处理范围是两倍权值T^T】

附代码。

#include
    
     #include
     
      #include
      
       #include
       
        #define ll long long#define inf 20021225#define db double#define mxn 400010using namespace std;const db pi=acos(-1.0);struct complex{    db x,y;    complex(){}    complex(db _x,db _y){x=_x,y=_y;}}f[mxn],g[mxn];complex operator +(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}complex operator -(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}complex operator *(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y);}int rev[mxn];int init(int n){    int lim=1,l=0;    while(lim
        
         >1]>>1)|((i&1)<<(l-1));    return lim;}void fft(complex *a,int n,int f){    for(int i=1;i
         
          i) swap(a[rev[i]],a[i]); for(int k=2;k<=n;k<<=1) { int mid = k>>1; complex Wn=complex(cos(pi/mid),f*sin(pi/mid)); for(int i=0;i