Description：

给定一个长度为 $N$ 的数组 $A[]$ ，求有多少对 $i,j,k$ （ $1\leqslant i<j<k\leqslant N$ ）满足 $A[k]-A[j]=A[j]-A[i]$ 。

$1\leqslant n\leqslant 10^5,1\leqslant a[i]\leqslant 30000$

Solution：

移个项就是 $a[j]=a[i]+a[k]$ ，那么一个暴力思路是枚举每个位置作为 $j$ ，把两边的生成函数乘起来累加答案，这样做是 $O(nA\log A)$ 的。

考虑怎么降低 $FFT$ 的次数， $n\leqslant 10^5$ 意味着我们可以用一些看上去不太优秀的做法。可以根号分治，每根号个分一块，然后对于有两个在同一块里的暴力做，否则把两边的生成函数 $FFT$ 起来累加答案。

.需要一些卡常，比如 $f$ 数组只用开到 $65536$ ，由于 $FFT$ 常数巨大所以要把块开大一点，大概开 $50$ 个块就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

} 

int n;

#define MAXN 100010

int v[MAXN];

#define MAXV 65538

#define MAXB 51

#define BLO 2000

struct comp

{

	double r,i;

	comp(double r_ = 0.0,double i_ = 0.0){r = r_;i = i_;}

};

comp operator + (comp a,comp b){return (comp){a.r + b.r,a.i + b.i};}

comp operator - (comp a,comp b){return (comp){a.r - b.r,a.i - b.i};}

comp operator * (comp a,comp b){return (comp){a.r * b.r - a.i * b.i,a.r * b.i + a.i * b.r};}

int rev[MAXV];

const double PI = acos(-1);

struct poly

{

	comp f[MAXV];

	int len;

	inline void FFT(comp f[],int l,int type)

	{

		for(register int i = 0;i < l;++i)

		{

			if(i < rev[i])swap(f[i],f[rev[i]]);

		}

		for(register int i = 2;i <= l;i = i << 1)

		{

			register comp wn = (comp){cos(-type * 2 * PI / i),sin(-type * 2 * PI / i)};

			for(register int j = 0;j < l;j += i)

			{

				register comp w = (comp){1,0};

				for(register int k = j;k < j + i / 2;++k)

				{

					register comp u = f[k],t = w * f[k + i / 2];

					f[k] = u + t;

					f[k + i / 2] = u - t;

					w = w * wn;

				}

			}

		}

		if(type == -1)

		{

			for(register int i = 0;i < l;++i)f[i].r /= l;

		}

		return;

	}

	friend poly operator + (poly a,poly b)

	{

		register int l = max(a.len,b.len);

		for(register int i = 0;i < l;++i)a.f[i] = a.f[i] + b.f[i];

		a.len = l;

		return a;

	}

	friend poly operator * (poly a,poly b)

	{

		register int n = max(a.len,b.len);

		register int l = 0,len = 1;

		for(;len < (n << 1);len = len << 1,++l);

		for(register int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

		a.FFT(a.f,len,1);b.FFT(b.f,len,1);

		for(register int i = 0;i < len;++i)a.f[i] = a.f[i] * b.f[i];

		a.FFT(a.f,len,-1);

		while(int(a.f[len - 1].r + 0.5) == 0)--len;

		a.len = len;

		return a;

	}

}pre[MAXB],suf[MAXB];

#define V 30010

int cnt[V];

int block,pos[MAXN];

int lef[MAXB],rig[MAXB];

int main()

{

	scanf("%d",&n);

	for(register int i = 1;i <= n;++i)v[i] = rd();

	register int blo = BLO;

	memset(lef,0x3f,sizeof(lef));

	for(register int i = 1;i <= n;++i)

	{

		pos[i] = (i - 1) / blo + 1;

	}

	block = pos[n];

	for(int i = 1;i <= block;++i)

	{

		lef[i] = (i - 1) * blo + 1;

		rig[i] = i * blo;

	}

	rig[block] = n;

	register long long ans = 0;

	for(register int i = 1;i <= block;++i)

	{

		for(register int j = lef[i];j <= rig[i];++j)for(register int k = j + 1;k <= rig[i];++k)

			if(0 <= 2 * v[j] - v[k] && 2 * v[j] - v[k] < V)ans += cnt[2 * v[j] - v[k]];

		for(register int j = lef[i];j <= rig[i];++j)++cnt[v[j]];

	}

	memset(cnt,0,sizeof(cnt));

	for(register int i = block;i >= 1;--i)

	{

		for(register int j = rig[i];j >= lef[i];--j)for(register int k = j - 1;k >= lef[i];--k)

			if(0 <= 2 * v[j] - v[k] && 2 * v[j] - v[k] < V)ans += cnt[2 * v[j] - v[k]];

		for(register int j = lef[i];j <= rig[i];++j)++cnt[v[j]];

	}

	memset(cnt,0,sizeof(cnt));

	for(register int i = 1;i <= block;++i)

	{

		for(register int j = lef[i];j <= rig[i];++j)

		{

			for(register int k = j + 1;k <= rig[i];++k)

			{

				if(0 <= 2 * v[j] - v[k] && 2 * v[j] - v[k] < V)ans += cnt[2 * v[j] - v[k]];

			}

			++cnt[v[j]];

		}

		for(register int j = lef[i];j <= rig[i];++j)cnt[v[j]] = 0;

	}

	for(register int i = 1;i <= block;++i)

	{

		if(i != 1)pre[i] = pre[i - 1];

		for(register int j = lef[i];j <= rig[i];++j)

		{

			++pre[i].f[v[j]].r;

			pre[i].len = max(pre[i].len,v[j] + 1);

		}

	}

	for(register int i = block;i >= 1;--i)

	{

		if(i != block)suf[i] = suf[i + 1];

		for(register int j = lef[i];j <= rig[i];++j)

		{

			++suf[i].f[v[j]].r;

			suf[i].len = max(suf[i].len,v[j] + 1);

		}

	}

	poly k;

	for(register int i = 2;i < block;++i)

	{

		k = pre[i - 1] * suf[i + 1];

		for(register int j = lef[i];j <= rig[i];++j)

		{

			ans += int(k.f[2 * v[j]].r + 0.5);

		}

	}

	cout << ans << endl;

	return 0;

}