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

· · 题解

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

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

你开始瞪眼法。你注意力惊人，发现 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，并且每题的罚时都比往常多五分钟，包含了开题的加载时间，提交的加载时间。

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

#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;
}