解题报告：

记录 A_i 为长度为 i 的树枝的数量，并让 A 对它本身做 FFT，得到任意选两个树枝能得到的各个和的数量。枚举第三边，

计算出所有两边之和大于第三条边的方案数，并把前两条边包含最长边的情况减掉就是答案。

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define ll __int64 9 #define pi acos(-1.0) 10 using namespace std; 11 const int MAX = 400002; 12 //复数结构体 13 struct complex{ 14 double r,i; 15 complex(double R=0,double I=0){ 16 r=R;i=I; 17 } 18 complex operator+(const complex &a){ 19 return complex(r+a.r,i+a.i); 20 } 21 complex operator-(const complex &a){ 22 return complex(r-a.r,i-a.i); 23 } 24 complex operator*(const complex &a){ 25 return complex(r*a.r-i*a.i,r*a.i+i*a.r); 26 } 27 }; 28 /* 29 *进行FFT和IFFT前的反转变换 30 *位置i和i的二进制反转后位置互换，(如001反转后就是100) 31 *len必须去2的幂 32 */ 33 void change(complex x[],int len){ 34 int i,j,k; 35 for(i = 1, j = len>>1; i 
             
              >1; 40 while (j >= k){ 41 j -= k; 42 k >>= 1; 43 } 44 if (j < k) j += k; 45 } 46 } 47 /* 48 *做FFT O(nLogn) 49 *len必须为2^n形式，不足则补0 50 *on=1时是DFT，on=-1时是IDFT 51 */ 52 void fft (complex x[],int len,int on){ 53 change(x,len); //调用反转置换 54 for (int i=2;i<=len;i<<=1){ //控制层次 55 //初始化单位复根 56 complex wn(cos(on*2*pi/i),sin(on*2*pi/i)); 57 for (int j=0;j
              
               >t; 81 while(t--){ 82 cin>>n; 83 memset(num,0,sizeof(num)); 84 for (i=0;i
               
                >a[i]; 86 num[a[i]]++; 87 } 88 sort(a,a+n); 89 len1 = a[n-1]+1; 90 len = 1; 91 while (len<2*len1) len<<=1; 92 for (i=0;i