bzoj3509.cc

#include #include #include #include

using namespace std;

typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)

struct cplx { double r, i; cplx() {} cplx(double rx, double ix) { r = rx, i = ix; } }; inline cplx operator +(const cplx& a, const cplx& b) { return cplx(a. r + b. r, a. i + b. i); } inline cplx operator -(const cplx& a, const cplx& b) { return cplx(a. r - b. r, a. i - b. i); } inline cplx operator *(const cplx& a, const cplx& b) { return cplx(a. r * b. r - a. i * b. i, a. r * b. i + a. i * b. r); }

const int maxn = 100009; const int bsz = 3000; const int maxv = 66009; const int maxa = 30000; const int fm = 1 « 16; const int maxl = 19; const double pi = acos(-1);

int n, a[maxn], b[maxv], c[maxv]; dint ans, d[maxv]; cplx wo[maxl];

void fftPre() { for (int i = 0; i < maxl; ++ i) { double tht(pi * 2 / (1 « i)); wo[i] = cplx(cos(tht), sin(tht)); } }

void calcInside(int le, int re) { static int v[maxa + 9]; memset(v, 0, sizeof(v)); for (int i = le; i < re; ++ i) { ans += v[a[i]]; for (int j = le; j < i; ++ j) { int nv(a[i] * 2 - a[j]); if (nv >= 0 && nv <= maxa) { ++ v[nv]; ans += c[nv]; } nv = a[j] * 2 - a[i]; if (nv >= 0 && nv <= maxa) ans += b[nv]; } } }

void radar(cplx* a, int n) { for (int i = 1, j = n » 1, k; i < n - 1; ++ i) { if (i < j) swap(a[i], a[j]); for (k = n » 1; k <= j; j -= k, k »= 1); if (j <= k) j += k; } }

void fft(cplx* a, int n, bool rv) { radar(a, n); for (int l = 2, lv = 1; l <= n; l «= 1, ++ lv) { cplx w0(wo[lv]); if (rv) w0. i = -w0. i; for (int i = 0; i < n; i += l) { cplx w(1, 0); for (int j = i; j < i + (l » 1); ++ j, w = w * w0) { cplx x(a[j]), y(w * a[j + (l » 1)]); a[j] = x + y; a[j + (l » 1)] = x - y; } } } if (rv) for (int i = 0; i < n; ++ i) a[i]. r /= n; }

void faltung(int le, int re) { static cplx x[maxv], y[maxv], z[maxv]; for (int i = 0; i < fm; ++ i) { x[i] = cplx(b[i], 0); y[i] = cplx(c[i], 0); } fft(x, fm, 0); fft(y, fm, 0); for (int i = 0; i < fm; ++ i) z[i] = x[i] * y[i]; fft(z, fm, 1); for (int i = 0; i < fm; ++ i) d[i] = _l (z[i]. r + 0.4999); for (int i = le; i < re; ++ i) ans += d[a[i] * 2]; }

int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif

fftPre();
scanf("%d", &n);
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
for (int i = 0; i < n; ++ i) {
	scanf("%d", a + i);
	++ c[a[i]];
}
for (int i = 0; i < n; i += bsz) {
	int j(min(i + bsz, n));
	for (int k = i; k < j; ++ k)
		-- c[a[k]];
	calcInside(i, j);
	if (i > 0 && j < n)
		faltung(i, j);
	for (int k = i; k < j; ++ k)
		++ b[a[k]];
}
printf(lld "\n", ans);

}

Comments