Given N integers in the range [?50000,50000], how many ways are there to pick three integers ai, aj, ak, such that i, j, k are pairwise distinct and ai+aj=ak? Two ways are different if their ordered triple (i,j,k) of indices are different.

Input

The first line of input consists of a single integer N (1≤N≤200000). The next line consists of N space-separated integers a1,a2,…,aN.

Output

Output an integer representing the number of ways.

Sample Input 1

4
1 2 3 4

Sample Output 1

4

Sample Input 2

6
1 1 3 3 4 6

Sample Output 2

10

題意

從輸入數(shù)據(jù)中找這樣的組合 ( i , j , k ) , 使$a_i$+$a_j$=$a_k$。輸出組數(shù)。

題解

num[k]表示（ai,aj）= k的個(gè)數(shù)。然后將ai = aj的那種重復(fù)的去掉。

然后計(jì)算當(dāng)a[i] = k時(shí)的（i,j,k）有多少種，很明顯就是 num[ a[i]]種,

注意有一種情況是有0的時(shí)候,因?yàn)橛锌赡軙?huì)自己加了0也等于ai 。所以要統(tǒng)計(jì)一下0有多少個(gè),減了0就可以了,注意(i,j)也是有順序要求的,（i,j）和(j,i)是2個(gè)不同的,所以還要處理有0的時(shí)候要乘以2倍。
然后是因?yàn)橛胸?fù)數(shù),我們要全部都加上50000變成正數(shù)就好了。

（HDU4609的變形）

思路

1. 輸入數(shù)據(jù)，保存在數(shù)組a中，輸入時(shí)記錄0的個(gè)數(shù)（zero）。
2. 將每個(gè)數(shù)字出現(xiàn)的個(gè)數(shù)保存在num數(shù)組中，因?yàn)橛胸?fù)數(shù)，保存的時(shí)候+50000。
3. 將數(shù)組a排序，a的最大值+50000就是num數(shù)組卷積之前的長(zhǎng)度。
4. 卷積num數(shù)組時(shí)，長(zhǎng)度要增長(zhǎng)為一個(gè)大于卷積之前長(zhǎng)度*2-1的2的整數(shù)次冪。
5. 由于涉及到復(fù)數(shù)，將num數(shù)組轉(zhuǎn)化為復(fù)數(shù)數(shù)組F，num數(shù)組輸入到a的最大值處（len1），增長(zhǎng)的長(zhǎng)度（len1到len）置為0.
6. 計(jì)算卷積：先用FFT法求加長(zhǎng)序列的DFT頻譜（執(zhí)行fft函數(shù)后的F數(shù)組），再將此時(shí)的F數(shù)組各項(xiàng)平方，再用IFFT求DFT頻譜乘積的逆變換，便得兩序列的離散線卷積。
7. 將計(jì)算卷積之后的F數(shù)組的實(shí)部返回到num數(shù)組中。此時(shí)num[k+100000]的值為i+j=k的組數(shù)。公式是這樣的 $\sum_{i+j=k}^{i,j<n}a_ib_j,k=0,1,...,2n-1$ 。
8. 由于i和j不能相同，把數(shù)組a中所有元素*2對(duì)應(yīng)位置的num數(shù)組卷積-1.
9. 用數(shù)組a中的元素搜索num數(shù)組，將num數(shù)組的元素累加，并減去0個(gè)數(shù)的兩倍。如果a中的元素本身是0，減去zero-1的兩倍。
10. 輸出結(jié)果。

AC代碼

#include <iostream>
#include <cmath>   
#include <algorithm>   
using namespace std;  

const int N = 2e5+10;  
const double pi = acos(-1.0);  


struct Complex{  
    double r,i;  
    Complex(double r=0,double i=0):r(r),i(i){
        //聲明復(fù)數(shù)：Complex XXX(XX,XX);
    };  
    //定義復(fù)數(shù)的加減乘運(yùn)算
    Complex operator+(const Complex &rhs){  
        return Complex(r + rhs.r,i + rhs.i);  
    }  
    Complex operator-(const Complex &rhs){  
        return Complex(r - rhs.r,i - rhs.i);  
    } 

    Complex operator*(const Complex &rhs){  
        return Complex(r*rhs.r - i*rhs.i,i*rhs.r + r*rhs.i);  
    } 

};

int len;
long long a[4*N];    
Complex F[4*N];    
long long num[4*N];  //每個(gè)數(shù)字出現(xiàn)的個(gè)數(shù)
int n;  
long long zero = 0;   //輸入值中0的個(gè)數(shù)
 

void rader(Complex F[],int len){ //len = 2^M,reverse F[i] with  F[j] j為i二進(jìn)制反轉(zhuǎn)   
    int j = len >> 1;  
    for(int i = 1;i < len - 1;++i){  
        if(i < j) swap(F[i],F[j]);  // reverse  
        int k = len>>1;  
        while(j>=k){  
            j -= k;  
            k >>= 1;  
        }  
        if(j < k) j += k;  
    }  
} 
//FFT  
void FFT(Complex F[],int len,int t){   
    for(int h = 2;h <= len; h <<= 1){ //分治后計(jì)算長(zhǎng)度為h的DFT   
        Complex wn(cos(-t * 2 * pi / h) , sin( -t * 2 * pi / h)); //單位復(fù)根e^(2*PI/m)用歐拉公式展開  
        for(int j = 0;j < len;j += h){
            Complex E(1,0); //旋轉(zhuǎn)因子  
            for(int k = j;k < j + h / 2; ++k){  
                Complex u = F[k];  
                Complex v = E * F[k + h / 2];  
                F[k] = u + v; //蝴蝶合并操作  
                F[k + h / 2] = u - v;  
                E = E * wn; //更新旋轉(zhuǎn)因子  
            }  
        }  
    }  
    if(t == -1){   //IDFT  離散傅利葉逆變換
        for(int i = 0;i < len; ++i){
            F[i].r /= len;  
        }
    }
}  
  
//卷積   
void Conv(Complex F[],int len){  
    //用FFT法求加長(zhǎng)序列的DFT頻譜
    FFT(F,len,1);  
    //計(jì)算DFT頻譜的平方
    for(long long i = 0; i < len; ++i){
        F[i] = F[i] * F[i];  
    }
    //用IFFT求DFT頻譜乘積的逆變換，便得兩序列的離散線卷積
    FFT(F,len,-1);  
}  
  
int main(int argc, char *argv[]){  
    //初始化 輸入數(shù)據(jù)
    cin >> n;
    memset(num,0,sizeof(num));             
    for(int i = 0; i < n; i++){    
        cin >> a[i];  
        if(a[i] == 0){
            zero++; 
        } 
        num[a[i] + 50000]++;    
    }      
    sort(a, a + n);    
    int len1 = a[n-1] + 50000 + 1; // 輸入最大值+50001 
    len = 1; 
    //計(jì)算卷積后F數(shù)組長(zhǎng)度 使len為2的整數(shù)次冪 并且 len >= 2 * len1 - 1  
    while(len < len1 * 2){
        len <<= 1;  
    }
    //num數(shù)組變?yōu)閺?fù)數(shù)形式
    for(int i = 0; i < len1; i++){    
        F[i] = Complex(num[i],0);    
    }
    //初始化F數(shù)組
    for(int i = len1; i < len; i++){   
        F[i] = Complex(0,0);    
    } 
    //計(jì)算卷積 
    Conv(F,len);  
    //num數(shù)組現(xiàn)在是卷積后的結(jié)果，num[k+100000]的值為i+j=k的組數(shù)    
    for(int i = 0; i < len; i++){    
        num[i] = (long long)(F[i].r + 0.5); //四舍五入   
    }     
    //本身和本身組合是不行的,減掉取兩個(gè)相同的組合  
    for(int i = 0; i < n; i++){    
        num[a[i] + a[i] + 2 * 50000]--;   
    }
    long long cnt = 0; //組數(shù)
    //找到輸入在num數(shù)組中對(duì)應(yīng)的位置 計(jì)算cnt 對(duì)0進(jìn)行特殊處理 
    for(int i = 0; i < n; i++){    
       if(a[i] != 0){  
         cnt += num[a[i] + 2 * 50000];  
         cnt -= zero * 2;  
       }else{  
            cnt += num[a[i] + 2 * 50000];  
            cnt -= (zero - 1) * 2;  
       }  
    }    
    cout << cnt << endl;   
    return 0;  
}