首页 > 其他 > 详细

SPOJ 8372. Triple Sums

时间:2014-10-07 17:04:24      阅读:441      评论:0      收藏:0      [点我收藏+]

8372. Triple Sums

Problem code: TSUM

 

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.

Constraints:

N <= 40000, |si| <= 20000

Input

The first line of input contains a single integer N.
Each of the next N lines contain an element of s.

Output

Print the solution for each possible sum in the following format:
sum_value : number_of_triples

Smaller sum values should be printed first.

Example

Input:

5
-1
2
3
0
5
Output:
1 : 1
2 : 1
4 : 2
5 : 1
6 : 1
7 : 2
8 : 1
10 : 1

Explanation:
4 can be obtained using triples ( 0, 1, 2 ) and ( 0, 3, 4 ).
7 can be obtained using triples ( 0, 2, 4 ) and ( 1, 3, 4 ).

Note: a triple is considered the same as any of its permutations.

 


用一个系数为该位指数在S中出现次数的多项式\(P\)来表示某位上指数的一次表示方式,那么三次表示方式就是\(P^3\),然后由于要求三元组的元素在S中的序数不同,容斥原理判重即可。

#include <bits/stdc++.h>
using namespace std;
typedef complex<long double> Complex;

const int maxn = 1 << 17;
const int base = 20000;
void DFT(Complex *a, int N, int flag) {
    for(int i = (N >> 1), j = 1, k; j < N; i ^= k, ++j) {
        if(i < j) swap(a[i], a[j]);
        for(k = (N >> 1); i & k; i ^= k, k >>= 1);
    }
    for(int n = 2; n <= N; n <<= 1) {
        Complex Wn = Complex(cos(flag * M_PI * 2 / n), sin(flag * M_PI * 2 / n));
        for(int i = 0; i < N; i += n) {
            Complex W = Complex(1.0, 0.0);
            for(int j = i; j < i + (n >> 1); W = W * Wn, ++j) {
                Complex u = a[j], v = W * a[j + (n >> 1)];
                a[j] = u + v;
                a[j + (n >> 1)] = u - v;
            }
        }
    }
}
int a[maxn], b[maxn], c[maxn];
Complex A[maxn], B[maxn], C[maxn];
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        x += base;
        ++a[x];
        ++b[x + x];
        ++c[x + x + x];
    }
    int N = maxn;
    for(int i = 0; i < N; ++i) {
        A[i] = a[i], B[i] = b[i];
    }
    DFT(A, N, 1);
    DFT(B, N, 1);
    for(int i = 0; i < N; ++i) {
        C[i] = A[i] * (A[i] * A[i] - 3.0l * B[i]);
    }
    DFT(C, N, -1);
    for(int i = 0; i < N; ++i) {
        long long ans = ((long long)(C[i].real() / N + 0.5) + 2 * c[i]) / 6;
        if(ans != 0) {
            printf("%d : %lld\n", i - 60000, ans);
        }
    }
    return 0;
}

bubuko.com,布布扣

 

SPOJ 8372. Triple Sums

原文:http://www.cnblogs.com/hzf-sbit/p/4009455.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!