Triple sum

/* You're given a sequence s of N distinct integers.
Consider all the possible sums of three integers from the sequence at three different indicies.
For each obtainable sum output the number of different triples of indicies that generate it.
SPOJ triple sum
solution : The general meaning of the question: give you N numbers, and then pick any three numbers and sum them, let you output the sum of the possible and corresponding to the number of programs.
        Since it is addition, consider using the generator function, multiplying two generator functions to get the sum of any two items, and the three are the same. Since |si| <=20000, the si is first enlarged by 20,000 to prevent negative numbers. Let A be the corresponding generator function, we can find that the result of A*A*A is repeated. A*A*A=three numbers are the same + two of them are the same + three numbers are not the same. So consider the tolerance, minus the repetition. Let A*A*A denote the whole, B denote two identical numbers, then A*B=two of them are the same + three numbers are different. Consider again the coefficients of the repulsion, where the two numbers are the same, the two numbers can be combined in three positions, C(3,2)=3. So the answer is to subtract 3*A*B. The current answer is A*A*A-3*A*B. We found that the three numbers were not calculated the same twice, so I made up for it. With C, I took three identical numbers, and the answer became A*A*A-3*A*B+2*C. It is now guaranteed that the three numbers are not the same, but the combination of three different numbers has 3!, so the final answer is divided by 6. See the code for details.
*/
  typedef complex < double > base ;
  const double PI = 2*acos( 0.0 );

void fft ( vector < base > & a, bool invert ) {
    int n = ( int ) a. size ( ) ;

    for ( int i = 1 , j = 0 ; i < n ; ++ i ) {
        int bit = n >> 1 ;
        for ( ; j >= bit ; bit >>= 1 )
            j -= bit ;
        j += bit ;
        if ( i < j )
            swap ( a [ i ] , a [ j ] ) ;
    }

    for ( int len = 2 ; len <= n ; len <<= 1 ) {
        double ang = 2 * PI / len * ( invert ? - 1 : 1 ) ;
        base wlen ( cos ( ang ) , sin ( ang ) ) ;
        for ( int i = 0 ; i < n ; i += len ) {
            base w ( 1 ) ;
            for ( int j = 0 ; j < len / 2 ; ++ j ) {
                base u = a [ i + j ] ,  v = a [ i + j + len / 2 ] * w ;
                a [ i + j ] = u + v ;
                a [ i + j + len / 2 ] = u - v ;
                w *= wlen ;
            }
        }
    }
    if ( invert )
        for ( int i = 0 ; i < n ; ++ i )
            a [ i ] /= n ;
}

void multiply ( const vector < ll > & a, const vector < ll > & b, vector < ll > & res ) {
    vector < base > fa ( a. begin ( ) , a. end ( ) ) ,  fb ( b. begin ( ) , b. end ( ) ) ;
    size_t n = 1 ;
    while ( n < max ( a. size ( ) , b. size ( ) ) )  n <<= 1 ;
    n <<= 1 ;
    fa. resize ( n ) ,  fb. resize ( n ) ;

    fft ( fa, false ) ,  fft ( fb, false ) ;
    for ( size_t i = 0 ; i < n ; ++ i )
        fa [ i ] *= fb [ i ] ;
    fft ( fa, true ) ;

    res. resize ( n ) ;
    for ( size_t i = 0 ; i < n ; ++ i )
        res [ i ] = (ll)( fa [ i ] . real ( ) + 0.5 ) ;
    while(res.size()>1&&res.back()==0)res.pop_back();
    /*  int carry = 0 ;
    for ( size_t i = 0 ; i < n ; ++ i ) {
        res [ i ] += carry ;
        carry = res [ i ] / 10 ;
        res [ i ] %= 10 ;
    }*/
}



int main(){
   // booster();
    //read("input.txt");

        vi a(81000,0);vi b(81000,0);vi c(150000,0);
        vi res,res2;
        int n,k;
        int mx = 0;
        scani(n);
        for(int i = 0;i<n;i++){
            int x;
            scani(x);
            a[x+MAX]++;
            b[x+x+MAX+MAX]++;
            c[x+x+x+MAX+MAX+MAX]++;
        }

        multiply(a,a,res);
        multiply(res,a,res);
        multiply(a,b,res2);
        for(int i = 0;i<res.size();i++){
            res[i] = (res[i] - 3*res2[i] + 2*c[i])/6;
        }
        for(int i = 0;i<res.size();i++)if(res[i]>EPS)printf("%d : %d\n",i - 3*(MAX) ,res[i]);



    return 0;
}