板子大赛之即使阿克但被【数据删除】击落导致 rk 204

你是一名信息学竞赛选手，你精通网络，这一天，你打开 AtCoder，却发现加载一个页面需要一分钟，于是你开始打 ABC。

给定 $n$ 个不同的正整数 $A_1,A_2,\cdots,A_n$ 。一个三元组 $(x,y,z)$ 是好的，当且仅当 $x<y<z$ 且 $y-x=z-y$ 。你可以任意选出三个数组成三元组，问有多少种方法能组成一个好的三元组。两种方法不同仅当你选择的数下标至少一个不同。

$n\leq 10^6,A_i\leq10^6$ 。

你开始瞪眼法。你注意力惊人，发现

y-x=z-y

等价于

2y=x+z

。于是你决定枚举

y

统计合法的

(x,z)

个数：

\text{Answer}=\sum_{i=1}^n\sum_{1\leq a<b\leq n}[A_a+A_b=2A_i].

于是你把这个放进有关值域

V

的桶中，

c_i

表示等于

i

的数个数：

\text{Answer}=\sum_{i=1}^V c_i\sum_{j=1}^{i-1} c_jc_{2i-j}.

你发现，后面这个求和像极了一个卷积。于是你使用了多项式，得到了数组

C

：

C_i=\sum_{j=1}^{i-1}c_jc_{i-j}.

你发现对于一个合法的

(x,y,z)

，

(x,y,z)

和

(z,y,x)

在卷积中都被统计，同时

(y,y,y)

也被统计，所以你去掉了重复和非法的方案。那么答案就是：

\text{Answer}=\sum_{i=1}^n\frac{C_{2A_i}-1}{2}.

你愉快地敲完了 FFT。交了一发。你的网速将你罚时一分钟，并在这一分钟之后成功提交了你的代码。通过了。你成功 AK 了 ABC392。

你愉快地打开榜单，却发现你打不开榜单，榜单保持在 Loading 状态。

赛后，你发现你在 AtCoder 打 ABC 时糟糕的网络状况。你关闭了它，然后成功打开榜单，却发现你是 rk 204，并且每题的罚时都比往常多五分钟，包含了开题的加载时间，提交的加载时间。

祝大家在打比赛的时候都有一个优良的网络环境。

CPP

#include <bits/stdc++.h>
#define LL long long
using namespace std;

namespace COMPLEX {
struct Complex {
	long double real, imag;
	Complex() { real = 0; imag = 0; return ; }
	Complex(long double a, long double b) { real = a, imag = b; return ; }
	const void operator = (const Complex& b) {
		real = b.real, imag = b.imag; return ;
	}
};
const Complex operator + (const Complex& a, const Complex& b) {
	return Complex(a.real + b.real, a.imag + b.imag);
}
const Complex operator - (const Complex& a, const Complex& b) {
	return Complex(a.real - b.real, a.imag - b.imag);
}
const Complex operator * (const Complex& a, const Complex& b) {
	return Complex(a.real * b.real - a.imag * b.imag, 
				   a.real * b.imag + a.imag * b.real);
}
const void operator += (Complex& a, const Complex& b) {
	a.real = a.real + b.real; a.imag = a.imag + b.imag; return ;
}
const void operator -= (Complex& a, const Complex& b) {
	a.real = a.real - b.real; a.imag = a.imag - b.imag; return ;
}
const void operator *= (Complex& a, const Complex& b) {
	a = Complex(a.real * b.real - a.imag * b.imag, 
				   a.real * b.imag + a.imag * b.real); return ;
}
} using namespace COMPLEX;

using comp = Complex;
const int N = 5e6 + 10;
int n, m; comp F[N], G[N];
namespace FFT {
const long double PI = acosl(-1);
void arrange(comp* F, int n) {
	for (int i = 0; i < n; i ++) {
		int x = 0;
		for (int j = 0; (1 << j) < n; j ++) 
			x = (x << 1) | ((i >> j) & 1);
		if (i > x) continue;
		swap(F[i], F[x]);
	} return ;
}
void DFT(comp* F, int n, int inv) {
	arrange(F, n); 
	for (int h = 2; h <= n; h <<= 1) {
		comp omega(cosl(2 * PI / h), sinl(inv * 2 * PI / h));
		for (int j = 0; j < n; j += h) {
			comp cur(1, 0);
			for (int k = j; k < j + h / 2; k ++) {
				comp a = F[k], b = F[k + h / 2] * cur;
				F[k] = a + b, F[k + h / 2] = a - b; cur *= omega;
			}
		}
	}
	if (inv == -1) {
		for (int i = 0; i < n; i ++) 
			F[i].real /= n, F[i].imag /= n;
	} return ;
}

} using FFT :: DFT;
using namespace FFT;
int trans(int x) {
	int t = 1;
	while (x) t <<= 1, x >>= 1;
	return t;
}
int A[N], cnt[N];
int main() {
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n; int m = 2e6 + 2;
	for (int i = 1; i <= n; i ++) { cin >> A[i]; cnt[A[i]] ++; }
	for (int i = 1; i <= m; i ++) F[i].real = F[i].imag = cnt[i];
	int len = 1; while (len < m) len <<= 1;
	DFT(F, len, 1);
	for (int i = 0; i < len; i ++) F[i] = F[i] * F[i];
	DFT(F, len, -1); LL Ans = 0;
	for (int i = 1; i <= n; i ++) Ans += (LL)(F[A[i] * 2].imag / 2 + 0.5) - 1;
	cout << Ans / 2 << "\n";
	return 0;
}

板子大赛之即使阿克但被【数据删除】击落导致 rk 204

文章操作

相关推荐

评论

板子大赛之即使阿克但被【数据删除】击落导致 rk 204