C++ 解法, 执行用时: 71ms, 内存消耗: 13340K, 提交时间: 2021-12-10 17:46:08

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 2e5 + 5;
const double pi = acos(-1);
int n, m, up = 1, l, r[N];
struct point {
	double x, y;
	point(double _x = 0, double _y = 0):x(_x), y(_y){}
	point operator +(point A) {return (point){x + A.x, y + A.y};}
	point operator -(point A) {return (point){x - A.x, y - A.y};}
	point operator *(point A) {return (point){x * A.x - y * A.y, x * A.y + y * A.x};}
}a[N], b[N], c[N];
void fft(point *f, int sz, int type) {
	for(int i = 1; i < sz; i++)
		if(i < r[i]) swap(f[i], f[r[i]]);
	for(int len = 1; len < sz; len <<= 1) {
		point wn(cos(pi / len), type * sin(pi / len));
		for(int j = 0; j < sz; j += len << 1) {
			point w(1, 0);
			for(int i = j; i < j + len; i++, w = w * wn) {
				point x = f[i], y = w * f[i + len];
				f[i] = x + y; f[i + len] = x - y;
			}
		}
	}
}
int A[N], B[N], C[N];
int main() {
	cin >> n;
	for(int i = 0; i < n; i++) {
		int x; cin >> x; x += 20000;
		A[x]++, B[2 * x]++, C[3 * x]++; m = max(m, x);
	}
	while(up <= 3 * m) up <<= 1, l++;
	for(int i = 0; i < up; i++)
		a[i].x = A[i], b[i].x = B[i];
	for(int i = 1; i < up; i++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	fft(a, up, 1), fft(b, up, 1);
	for(int i = 0; i < up; i++)
		c[i] = a[i] * (a[i] * a[i] - b[i] * 3);
	fft(c, up, -1);
	for(int i = 0; i < up; i++) {
		long long x = ((ll)(c[i].x / up + 0.5) + 2 * C[i]) / 6;
		if(x) printf("%d : %lld\n", i - 60000, x);
	}
	return 0;
}