题意是给三面墙(简化为一条轴)，然后给墙上的洞（简化成点），问多少直线可以从第一面墙穿出第三面墙。
要使三点共线，那么(b-a)=(c-b)即(a+c)=2*b
由于n是1e5所以O(n2)会超时。有两种做法
1.本题的任意两数相加的步骤类似多项式乘法，我们把a,c看成两个多项式的系数，然后用FFT，最后计算下b里每个元素*2指数的系数之和即可。注意数组的数可能有负数，整体+3e4即可。
查看代码
#pragma GCC optimize(2)
#include<iostream>
#include<cmath>
#include<complex>
#define int long long
using namespace std;
typedef complex<double> comp;
const comp I=comp(0, 1);
const double PI = acos(-1);
const int MAXN=500005;
comp d[150005],e[150005],f[150005];
int ans=0,a,c,b[150005];
int rev[MAXN * 3];
void fft(comp F[], int N, int sgn = 1)
{
int bit = __lg(N);
for (int i = 0; i < N; ++i)
{
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
if (i < rev[i])
swap(F[i], F[rev[i]]);
}
for (int l = 1; l < N; l <<= 1)
{
comp step = exp(sgn * PI / l * I);
for (int i = 0; i < N; i += l * 2)
{
comp cur(1, 0);
for (int k = i; k < i + l; ++k)
{
comp g = F[k], h = F[k + l] * cur;
F[k] = g + h, F[k + l] = g - h;
cur *= step;
}
}
}
if(sgn==-1)
{
for(int i=0;i<N;i++)
F[i]/=N;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int aa,bb,cv,zx=0,cx=0;
cin>>aa;
for(int i=1;i<=aa;i++)
{
cin>>a;
a+=30000;
zx=max(a,zx);
e[a]+=1;
}
cin>>bb;
for(int i=1;i<=bb;i++)
{
cin>>b[i];
b[i]+=30000;
}
cin>>cv;
for(int i=1;i<=cv;i++)
{
cin>>c;
c+=30000;
cx=max(cx,c);
f[c]+=1;
}
int A=1<<__lg(cx+zx+1)+1;
fft(e,A,1);
fft(f,A,1);
for(int i=0;i<A;i++)
d[i]=e[i]*f[i];
fft(d,A,-1);
for(int i=1;i<=bb;i++)
ans+=((d[b[i]*2].real())+0.1);//FFT+0.1避免浮点数的问题
cout<<ans;
return 0;
}2.用bitset解决。在CF看到的解法，比第一种简单且易于实现。
(b-a)=(c-b)，-> (-a+b)=(c-b)
那么我们将其中另一条反转下。因为b所在的点仅仅是0，那么反转后与运算为1的数目就是0位置b点可通过的方式数。
那么b的-1这个怎么找呢？从原图我们可以看到(0,-2)是符合条件的。 (-a+b)=(c-b)得知，需要一个+b一个-b，那么此时对准的孔洞只有一个
那么用bitset实现即可。在CF上第二种时间大概是第一种的10倍。
查看代码
//https://codeforces.com/gym/102920/problem/H
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<iostream>
#include<bitset>
#define int long long
using namespace std;
bitset<60005>a,c;
int b[50005],n,m,x;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
a[x+30000]=1;
}
cin>>m;
for(int i=1;i<=m;i++)cin>>b[i];
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
c[30000-x]=1;
}
int ans=0;
for(int i=1;i<=m;i++)
{
if(b[i]>0)
ans+=((a>>b[i])&(c<<b[i])).count();
else ans+=((a<<(-b[i]))&(c>>(-b[i]))).count();
}
cout<<ans;
return 0;
}