HDU 4609 3-idiots

原题链接
题意：给定n个线段长度，问任意选3个组成三角形的概率。
n<=1e5

假如我们能求出任意两个的长度，就可以选出第3条边了。如我们求出siz[i]表示任意两个不同的线段的和等于i的个数，那么枚举最长的一条边a[i]，那么任意两条比a[i]+1大的都行ans+=siz[a[i]+1]+...+siz[mx]，其次要减去选了a[i]自己的可能就是n-1,其次就是选了一大一小(n-i)*(i-1)，都比a[i]大(n-i)*(n-i-1)/2。
下面考虑如何求siz[i]，这就是经典的fft问题。构造多项式\(A(x)=num[0]+num[1]*x^1+...+num[n]*x^n\)，\(B(x)=num[0]+num[1]*x^1+...+num[n]*x^n\)，那么C(x)的i+j的系数就是独立选两条的和，接着num[a[i]+a[i]]--，减去自己选了两次，num[i]/=2，去掉选了两次的情况，即选了a[i]与a[j]，又选了a[j]与a[i]。

时间复杂度：\(O(nlogn)\)

#include 
using namespace std;                          
typedef long long ll;
const int maxn=2e6+10;
const double pi=acos(-1);
struct Complex{
    double x,y;
    friend Complex operator+(Complex x1,Complex y1)
    {
        return {x1.x+y1.x,x1.y+y1.y};
    }
    friend Complex operator-(Complex x1,Complex y1)
    {
        return {x1.x-y1.x,x1.y-y1.y};
    }
    friend Complex operator*(Complex x1,Complex y1)
    {
        return {x1.x*y1.x-x1.y*y1.y,x1.x*y1.y+x1.y*y1.x};
    }
}af[maxn],bf[maxn];
int rev[maxn];
void init(int n)
{
    rev[0]=0;
    for(int i=0;i>1]>>1;
        if(i&1) rev[i]|=n>>1;
    }
}
void fft(Complex a[],int n,int inv)
{
    for(int i=0;i>t;
    while(t--)
    {
        int n;cin>>n;
        memset(siz,0,sizeof(siz));
        for(int i=1;i<=n;i++)
        cin>>a[i],siz[a[i]]++;
        sort(a+1,a+1+n);
        int cnt=1;
        while(cnt<2*a[n]+1) cnt*=2;
        af[0]=bf[0]={0,0};
        for(int i=1;i