FFT应用总结
内容
只是一些简单的应用，更难一点的还没写完。。
感觉在学校没啥效率，整天瞎考试
bzoj3527
题意
给出$n$个$q_i$，且
$$F_j = \sum_{i< j}{q_iq_j\over (i – j)^2}-\sum_{i>j}{q_iq_j\over (i – j)^2}$$
求$E_i = {F_i\over q_i}$
题解
首先把$i,j$调一下，看着太难受了
$$F_i = \sum_{j< i}{q_iq_j\over (j – i)^2}-\sum_{j>i}{q_iq_j\over (j – i)^2}$$
这样就可以化式子了
$$
\begin{aligned}
E_i &= {F_i \over q_i}\\
&=\sum_{j< i}{q_j\over (j – i)^2}-\sum_{j>i}{q_j\over (j – i)^2}\\
&=\sum_{j=1}^{i-1}{q_j\over (j – i)^2}-\sum_{j=i+1}^n{q_j\over (j – i)^2}\\
&设 g_i = {1\over i^2}\;\;\; f_i = q_i\\
E_i &=\sum_{j=1}^{i-1}{f_jg_{i – j}}-\sum_{j=i+1}^n{f_jg_{j – i}}\\
\end{aligned}
$$
左边的式子显然是个卷积，现在看下右边的式子
$$\sum_{j = i+1}^nf_jg_{j – i}$$
可以换个元
$$\sum_{j + i = i+1}^nf_{j + i}g_{j + i – i}$$
等式两边同时减掉一个$i$。($g_0 = 0$可以直接化)
$$\sum_{j = 0}^{n -i}f_{j+i}g_j$$
再换元
$$\sum_{n-i-j=0}^{n-i}f_{n-i-j+i}g_{n-i-j}$$
化成
$$\sum_{j=0}^{n-i}f_{n-j}g_{n-i-j}$$
设$t = n-i$
$$\sum_{j = 0}^tf_{n-j}g_{t-j}$$
设$f’_i = f_{n-i}$
$$\sum_{j=0}^t f’_jg_{t-j}$$
。。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi=acos(-1.0);
const int N = 400010;
int n, m, r[N];
struct complex {
double x, y;
complex (double xx = 0, double yy = 0) {
x = xx, y = yy;
}
}a[N], b[N], o[N], a_o[N];
complex operator + (complex a,complex b) { return complex(a.x + b.x, a.y + b.y); }
complex operator - (complex a,complex b) { return complex(a.x - b.x, a.y - b.y); }
complex operator * (complex a,complex b) { return complex(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }
void init(int n) {
double t = 2 * pi / n;
for (int i = 0; i <= n; ++i) {
o[i] = complex(cos(2.0 * pi * i / n), sin(2.0 * pi * i / n));
a_o[i] = complex(cos(2.0 * pi * i / n),-1 * sin(2.0 * pi * i / n));
}
}
void fft(int n, complex *a, complex *w)
{
for (int i = 0; i < n; ++i)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int i = 2; i <= n; i <<= 1) {
int m = i >> 1;
for (int j = 0; j < n;j += i)
for (int k = 0; k < m; ++k) {
complex t = a[j + m + k] * w[n / i * k];
a[j + m + k] = a[j + k] - t;
a[j + k] = a[j + k] + t;
}
}
}
double ans[N], q[N];
main() {
static int n,m,fn,l=0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lf", &q[i]);
a[0].x = 0;
for (int i = 1; i <= n; ++i) a[i].x = q[i];
b[0].x = 0;
for (int i = 1; i <= n; ++i) b[i].x = 1.0 / i / i;
fn = 1;
while (fn <= n * 2) fn <<= 1, ++l;
for (int i = 0; i < fn; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
init(fn);
fft(fn, a, o);
fft(fn, b, o);
for (int i = 0; i <= fn; ++i) a[i] = a[i] * b[i];
fft(fn, a, a_o);
for (int i = 0; i <= n; ++i)
ans[i] = a[i].x / fn;
for (int i = 0; i <= n; ++i) a[i].x = q[n - i], a[i].y = 0;
for (int i = n + 1; i <= fn; ++i) a[i].x = 0, a[i].y = 0;
b[0].x = 0, b[0].y = 0;
for (int i = 1; i <= n; ++i) b[i].x = 1.0 / i / i, b[i].y = 0;
for (int i = n + 1; i <= fn; ++i) b[i].x = 0, b[i].y = 0;
fft(fn, a, o);
fft(fn, b, o);
for (int i = 0; i <= fn; ++i) a[i] = a[i] * b[i];
fft(fn, a, a_o);
for (int i = 1; i <= n; ++i)
ans[i] -= a[n - i].x / fn;
for (int i = 1; i <= n; ++i)
printf("%.2lf\n", ans[i]);
}
bzoj 2194
题意
求
$$c_k=\sum_{k\leq i< n}a_ib_{i-k}$$
题解
化式子吧。。
$$
\large
\begin{aligned}
c_k &= \sum_{k \leq i \leq n-1}a_ib_{i-k}\\
&= \sum_{0\leq i-k \leq n-k-1} a_ib_{i-k}\\
&= \sum_{0 \leq j \leq n-k-1} a_{j+k}b_j \;\;\;\;(j=i-k)\\
& 设 \; N=n-k-1,c’_N=c_k\\
c’_N &= \sum_{0 \leq j\leq N}a_{n-1-(N-j)}b_j\\
& 设 \; a’_{N-j}=a_{n-1-(N-j)},a’_{i}=a_{n-1-i}\\
c’_N &= \sum_{0 \leq j\leq N}a’_{N-j}b_j
\end{aligned}
$$
。。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi=acos(-1.0);
const int N = 400010;
int n, m, r[N];
struct complex {
double x, y;
complex (double xx = 0, double yy = 0) {
x = xx, y = yy;
}
}a[N], b[N], o[N], a_o[N];
complex operator + (complex a,complex b) { return complex(a.x + b.x, a.y + b.y); }
complex operator - (complex a,complex b) { return complex(a.x - b.x, a.y - b.y); }
complex operator * (complex a,complex b) { return complex(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }
void init(int n) {
double t = 2 * pi / n;
for (int i = 0; i <= n; ++i) {
o[i] = complex(cos(2.0 * pi * i / n), sin(2.0 * pi * i / n));
a_o[i] = complex(cos(2.0 * pi * i / n),-1 * sin(2.0 * pi * i / n));
}
}
void fft(int n, complex *a, complex *w)
{
for (int i = 0; i < n; ++i)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int i = 2; i <= n; i <<= 1) {
int m = i >> 1;
for (int j = 0; j < n;j += i)
for (int k = 0; k < m; ++k) {
complex t = a[j + m + k] * w[n / i * k];
a[j + m + k] = a[j + k] - t;
a[j + k] = a[j + k] + t;
}
}
}
double p[N], q[N], ans[N];
main() {
static int n,m,fn,l=0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%lf%lf", &p[i], &q[i]);
for (int i = 0; i <= n; ++i) a[i].x = p[n - i - 1];
for (int i = 0; i <= n; ++i) b[i].x = q[i];
fn = 1;
while (fn <= n * 2) fn <<= 1, ++l;
for (int i = 0; i < fn; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
init(fn);
fft(fn, a, o);
fft(fn, b, o);
for (int i = 0; i <= fn; ++i)
a[i] = a[i] * b[i];
fft(fn, a, a_o);
for (int i = 0; i < n; ++i)
ans[n - i - 1] = a[i].x / fn;
for (int i = 0; i < n ; ++i)
printf("%d\n", (int)(ans[i] + 0.5));
}
bzoj 3771
题意
给出$n$个物品，价值为别为$X_i$且各不相同，现在可以取$1$个、$2$个或$3$个，问每种价值和有几种情况？
*顺序不同算一种
题解
构造三个生成函数，系数是这个数出现了几次。$A$表示每种物品取一个的情况，$B$表示每种物品取二个的情况，$C$表示每种物品取三个的情况。
也就是对于每种物品价值$X_i$,A[Xi]++,B[2 * Xi]++,C[3 * Xi]++。
如果取$1$个物品，答案就是$A$。
如果取$2$个物品，$A^2$中有重复的$(X_i,X_i)$的情况，所以答案为$A^2-B$。
如果取$3$个物品，$A^3$中可能有$(X_i,X_i,X_i)(X_i,X_i,Y_i)(X_i,Y_i,X_i)(Y_i,X_i,X_i)$这几种重复的情况，而$A\times B$能够求出所有形容$(X_i,X_i,X_i)$和$(X_i,Y_i,Y_i)$的情况数。$(X_i,X_i,Y_i)(X_i,Y_i,X_i)(Y_i,X_i,X_i)$总的情况数=$(X_i,Y_i,Y_i)\times 3$，而$A\times B\times3$又会多减去了两次$(X_i,X_i,X_i)$，所以要用$C$加回来。所以答案为$A^3-3\times B\times A+2\times C$。又由于顺序不同算一种情况，因为每种物品价值都不一样，情况(2)/2,情况(3)/6。
总答案就是
$${A^3(x)-3A(x)·B(x)+2C(x)\over 6}+{A^2(x)-B(x)\over 2}+A(x)$$
注意可以一直用点值表达式形式算。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi=acos(-1.0);
const int N = 262194;
int n, m, r[N];
struct complex {
double x, y;
complex (double xx = 0, double yy = 0) {
x = xx, y = yy;
}
}a[N], b[N], c[N], o[N], a_o[N];
complex operator + (complex a,complex b) { return complex(a.x + b.x, a.y + b.y); }
complex operator - (complex a,complex b) { return complex(a.x - b.x, a.y - b.y); }
complex operator * (complex a,complex b) { return complex(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }
complex operator / (complex a,double b) { return complex(a.x / b, a.y / b); }
void init(int n) {
double t = 2 * pi / n;
for (int i = 0; i <= n; ++i) {
o[i] = complex(cos(2.0 * pi * i / n), sin(2.0 * pi * i / n));
a_o[i] = complex(cos(2.0 * pi * i / n),-1 * sin(2.0 * pi * i / n));
}
}
void fft(int n, complex *a, complex *w)
{
for (int i = 0; i < n; ++i)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int i = 2; i <= n; i <<= 1) {
int m = i >> 1;
for (int j = 0; j < n;j += i)
for (int k = 0; k < m; ++k) {
complex t = a[j + m + k] * w[n / i * k];
a[j + m + k] = a[j + k] - t;
a[j + k] = a[j + k] + t;
}
}
}
main() {
static int n, m, fn, x, l=0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
a[x].x += 1, b[x * 2].x += 1, c[x * 3].x += 1;
m = max(m, x * 3);
}
fn = 1;
while (fn <= m + m) fn <<= 1, ++l;
for (int i = 0; i < fn; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
init(fn);
fft(fn, a, o);
fft(fn, b, o);
fft(fn, c, o);
complex n2, n3, n6;
n2.x = 2, n2.y = 0;
n3.x = 3, n3.y = 0;
n6.x = 6, n6.y = 0;
for (int i = 0; i <= fn; ++i)
a[i] = ((a[i] * a[i] * a[i]) - n3 * a[i] * b[i] + n2 * c[i]) / 6.0 + (a[i] * a[i] - b[i]) / 2.0 + a[i];
fft(fn, a, a_o);
for (int i = 1; i <= m + m; ++i) {
long long ans = (long long) (a[i].x / fn + 0.5);
if (ans) printf("%d %d\n", i, ans);
}
}
bzoj 3513
题解
因为$a_i$的范围很小，可以搞个权值多项式，$A_i$表示长度为$i$的木棒出现了多少次
现在考虑求一个$B_i$表示两根木棒拼起来的权值多项式，显然
$$B_i = \sum A_j \times A_{i-j}$$
这是一个卷积的形式，直接fft求解
然后发现这样会出现自己和自己拼起来的情况，直接减掉即可
现在考虑求一下答案的补集，就是不能拼成三角形的情况，再拿1减掉就是答案。
我们对$B$求一个前缀和，那么$B_i$就表示了两根木棒拼起来小于等于$i$的有多少个
那么答案的补集就是$B_i\times A_i$，就是原始长度为$i$的个数乘上拼起来长度小于等于它的个数
因为能正着和倒着拼，所以要除2。最后别忘了除$C_n^3$，我们求的是概率。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int inline read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const double pi=acos(-1.0);
const int N = 300010;
int n, m, r[N];
struct complex {
double x, y;
complex (double xx = 0, double yy = 0) {
x = xx, y = yy;
}
}a[N], o[N], a_o[N];
complex operator + (complex a,complex b) { return complex(a.x + b.x, a.y + b.y); }
complex operator - (complex a,complex b) { return complex(a.x - b.x, a.y - b.y); }
complex operator * (complex a,complex b) { return complex(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }
void init(int n) {
double t = 2 * pi / n;
for (int i = 0; i <= n; ++i) {
o[i] = complex(cos(2.0 * pi * i / n), sin(2.0 * pi * i / n));
a_o[i] = complex(cos(2.0 * pi * i / n),-1 * sin(2.0 * pi * i / n));
}
}
void fft(int n, complex *a, complex *w) {
for (int i = 0; i < n; ++i)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int i = 2; i <= n; i <<= 1) {
int m = i >> 1;
for (int j = 0; j < n;j += i)
for (int k = 0; k < m; ++k) {
complex t = a[j + m + k] * w[n / i * k];
a[j + m + k] = a[j + k] - t;
a[j + k] = a[j + k] + t;
}
}
}
int x, ton[N];
long long te[N];
main() {
// freopen("da.txt","r",stdin);
static int n, fn, l, T;
T = read();
while (T--) {
scanf("%d", &n);
l = 0;
for (int i = 0; i <= fn; ++i) {
r[i] = 0;
a[i].x = 0, a[i].y = 0;
}
int mx = 0;
memset(ton, 0, sizeof ton);
for (int i = 1; i <= n; ++i)
x = read(), a[x].x += 1.0,
ton[x]++, mx = max(mx, x);
fn = 1;
while (fn <= mx + mx) fn <<= 1, ++l;
for (int i = 0; i < fn; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
init(fn);
fft(fn, a, o);
for (int i = 0; i <= fn; ++i)
a[i] = a[i] * a[i];
fft(fn, a, a_o);
for (int i = 0; i <= mx; ++i)
te[i] = (long long)(a[i].x / (double)fn + 0.5);
for (int i = 0; i <= mx >> 1; ++i)
te[i<<1] -= ton[i];
for (int i = 1; i <= mx; ++i)
te[i] += te[i - 1];
double ans = 0;
for (int i = 1; i <= mx; ++i)
ans += te[i] * ton[i];
double C = n * (n - 1.0) * (n - 2.0) / 6.0;
ans /= 2.0;
printf("%.7lf\n", 1.0 - ans / C);
}
}
bzoj 4259
题解
首先我们定义一个字符串的距离函数，对于两个长度都是$n$的字符串$A,B$，定义他们的距离为
$$dis(A,B) = \sum_{i = 0}^{n-1}(A_i – B_i)^2 [A_i != *][B_i!=*]$$
假如我们把所有星号都约定成$0$的话
$$dis(A,B) = \sum_{i = 0}^{n – 1}(A_i-B_i)^2A_iB_i$$
对于题目的话，首先发现题面里面写到$1\leq m\leq n\leq 300000$，也就是说第二个串要比第一个串要长
那么我们可以枚举第二个串的结尾位置来匹配，定义函数$f_i = dis(A,B[i – m + 1,i])$，那么
$$f_i = \sum_{i = 0}^{m – 1} (A_j – B_{i – m + 1 + j})^2A_jB_{i – m + 1 + j}$$
也就是，$f_i = 0$的时候表明$B$的这个子串和$A$成功匹配了
但是我们想凑出个卷积该怎么办呢？首先式子里面应该有个$i – j$，要构造出来一个的话必须把一个串翻转一下，那我们就把$A$串翻转一下。还有就是$B$的下标有点乱，需要化简一下。我们现在是一个枚举长度$m$，但是我们可以在$A$后面添加很多个$0$，让它变成一个枚举$i$的式子，这样就非常符合卷积的形式了：
$$
\begin{aligned}
f_i &= \sum_{j = 0}^i(A_j – B_{i – j})^2A_jB_{i – j}\\
&=\sum_{j = 0}^i(A_j^2-2A_jB_{i – j} + B_{i – j}^2)A_jB_{i – j}\\
&=\sum_{j = 0}^iA_j^3B_{i – j}-2\sum_{j = 0}^iA_j^2B_{i – j}^2+\sum_{j = 0}^iA_jB_{i – j}^3\\
\end{aligned}
$$
。。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi=acos(-1.0);
const int N = 1048576;
int n, m, r[N];
struct complex {
double x, y;
complex (double xx = 0, double yy = 0) {
x = xx, y = yy;
}
}a[N], b[N], c[N], o[N], a_o[N];
complex operator + (complex a,complex b) { return complex(a.x + b.x, a.y + b.y); }
complex operator - (complex a,complex b) { return complex(a.x - b.x, a.y - b.y); }
complex operator * (complex a,complex b) { return complex(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }
void init(int n) {
double t = 2 * pi / n;
for (int i = 0; i <= n; ++i) {
o[i] = complex(cos(2.0 * pi * i / n), sin(2.0 * pi * i / n));
a_o[i] = complex(cos(2.0 * pi * i / n),-1 * sin(2.0 * pi * i / n));
}
}
void fft(int n, complex *a, complex *w) {
for (int i = 0; i < n; ++i)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int i = 2; i <= n; i <<= 1) {
int m = i >> 1;
for (int j = 0; j < n; j += i)
for (int k = 0; k < m; ++k) {
complex t = a[j + m + k] * w[n / i * k];
a[j + m + k] = a[j + k] - t;
a[j + k] = a[j + k] + t;
}
}
}
int p[N], q[N], ans[N], top;
char s1[N], s2[N];
int tr(int x) { return x * x * x; }
int sq(int x) { return x * x; }
main() {
static int n, m, fn, l = 0;
scanf("%d%d", &m, &n);
scanf("%s%s", s1, s2);
n--, m--;
fn = 1;
while (fn <= n + m) fn <<= 1, ++l;
for (int i = 0; i < fn; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
init(fn);
for (int i = 0, j = m; i < j; i++, j--) swap(s1[i], s1[j]);
for (int i = 0; i <= m; ++i) if (s1[i] != '*') p[i] = s1[i] - 'a' + 1;
for (int i = 0; i <= n; ++i) if (s2[i] != '*') q[i] = s2[i] - 'a' + 1;
for (int i = 0; i <= fn; ++i) a[i].x = tr(p[i]), a[i].y = 0;
for (int i = 0; i <= fn; ++i) b[i].x = q[i], b[i].y = 0;
fft(fn, a, o), fft(fn, b, o);
for (int i = 0; i <= fn; ++i) c[i] = c[i] + a[i] * b[i];
for (int i = 0; i <= fn; ++i) a[i].x = p[i], a[i].y = 0;
for (int i = 0; i <= fn; ++i) b[i].x = tr(q[i]), b[i].y = 0;
fft(fn, a, o), fft(fn, b, o);
for (int i = 0; i <= fn; ++i) c[i] = c[i] + a[i] * b[i];
complex two; two.x = 2, two.y = 0;
for (int i = 0; i <= fn; ++i) a[i].x = sq(p[i]), a[i].y = 0;
for (int i = 0; i <= fn; ++i) b[i].x = sq(q[i]), b[i].y = 0;
fft(fn, a, o), fft(fn, b, o);
for (int i = 0; i <= fn; ++i) c[i] = c[i] - a[i] * b[i] * two;
fft(fn, c, a_o);
for (int i = 0; i <= fn; ++i) c[i].x = c[i].x / fn;
for (int i = m; i <= n; ++i) if (c[i].x < 0.5) ans[++top] = i - m + 1;
printf("%d\n", top);
for (int i = 1; i < top; ++i) printf("%d ", ans[i]);
if (top) printf("%d", ans[top]);
}
bzoj3509
题解
首先简单化下式子，发现$2A_j=A_i+A_k$
也就是说一个数在两边选两个数使得两数的和为这个数的两倍。
这样对这个数两边的数放到权值生成函数里面，fft一下再找这个数的两倍就可以了。
发现太慢了，$O(n^2\log n)$（这里就把$a_i$最大值也设成$n$了，懒）
这样就可以想到分块的思想，对于块内的暴力一下，块外的fft求下，就可以了。
算下复杂度是$O(\sqrt n \;n\log n+\sqrt n\; n)$
（需要有优越的调参技术
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const double pi=acos(-1.0);
const int N = 70010;
const int M = 100010;
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
using namespace std;
char BB[1 << 15], *S = BB, *T = BB;
int inline read()
{
int x=0, f=1;char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f=-1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int n, m, r[N];
struct complex {
double x, y;
complex (double xx = 0, double yy = 0) {
x = xx, y = yy;
}
}a[N], b[N];
complex operator + (complex a,complex b) { return complex(a.x + b.x, a.y + b.y); }
complex operator - (complex a,complex b) { return complex(a.x - b.x, a.y - b.y); }
complex operator * (complex a,complex b) { return complex(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }
complex operator / (complex a,double b) { return complex(a.x / b, a.y / b); }
void fft(int n, complex *a, int opt) {
for (int i = 0; i < n; ++i)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int k = 1; k < n; k <<= 1)
{
complex wn = complex(cos(pi / k), opt * sin(pi / k));
for (int i = 0; i < n; i += (k<<1))
{
complex w = complex(1, 0);
for (int j = 0; j < k; ++j, w = w * wn)
{
complex x = a[i + j], y = w * a[i + j + k];
a[i + j]= x + y,a[i + j + k]= x - y;
}
}
}
if (opt == -1) for (int i = 0; i < n; ++i) a[i] = a[i] / n;
}
double R[N], L[N];
long long anss;
int mx, t[M], blo;
main() {
// freopen("input.txt","r",stdin);
n = read();
for (int i = 1; i <= n; ++i)
t[i] = read(), mx = max(t[i], mx);
blo = min(n, (int)sqrt(n) * 6);
// blo = (int)sqrt(n);
for (int i = 1; i <= n; ++i) R[t[i]]++;
for (int i = 1; i <= n; i += blo) {
int l = i, r = min(n, i + blo - 1);
for (int j = l ; j <= r; ++j) R[t[j]]--;
for (int j = l ; j <= r; ++j) {
for (int k = j + 1; k <= r; ++k) {
int temp = t[k] * 2 - t[j];
if (temp >= 0) anss += (long long)R[temp];
temp = t[j] * 2 - t[k];
if (temp >= 0) anss += (long long)L[temp];
}
L[t[j]]++;
}
}
int l = 0, fn = 1;
while (fn <= (mx << 1)) fn <<= 1, ++l;
for (int i = 0; i <= fn; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
for (int i = 1; i <= n; i += blo) {
for (int j = 0; j < fn; ++j) a[j] = b[j] = complex(0,0);
int l = i, r = min(n, i + blo - 1);
for (int j = 1; j < l; ++j) a[t[j]].x += 1.0;
for (int j = r + 1; j <= n; ++j) b[t[j]].x += 1.0;
fft(fn, a, 1);
fft(fn, b, 1);
for (int i = 0; i <= fn; ++i)
a[i] = a[i] * b[i];
fft(fn, a, -1);
for (int j = l; j <= r; ++j) anss += (long long)(a[t[j] * 2].x + 0.1);
// for (int j = l; j <= r; ++j) printf("%d ", (long long)(ans[t[j] * 2] + 0.5));puts("");
// printf("%I64d\n", anss);
}
printf("%lld\n", anss);
}