BZOJ4836 [Lydsy1704月赛]二元运算

Vexoben

Jul 15, 2018

It takes 6 minutes to read this article.

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4836

（刷新以获取数学公式）

题解

不妨先考虑只有一种运算且没有取值范围的限制条件的时候。

令 $A_i$ 表示数组 $a$ 中 $i$ 的出现次数， $B_i$ 同理，只需要计算：

$C_k=\sum_{i+j=k}A_i*B_j$ $D_k=\sum_{i-j=k}A_i*B_j$

则 $C_i$ 就是只有加法的答案， $D_i$ 就是只有减法的答案。这是FFT模板题。

那么加上限制条件呢？分治FFT可以解决。

Solve(l,r)表示计算 $A[l..r]*B[l..r]$

答案可以分为四部分：

1、 $A[l..mid]*B[mid+1..r]$ 这部分贡献全部是加法

2、 $A[mid+1..r]*B[l..mid]$ 这部分贡献全部是减法

3、Solve(l,mid)； 4、Solve(mid+1,r)

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1<<17;
const double pi=acos(-1.0);

LL ans[N];
int n,m,q,a[N],b[N],rev[N];
struct C {
	double r,i;
	C(){}
	C(double x,double y) {r=x,i=y;}
	C operator + (C x) {return C(r+x.r,i+x.i);}
	C operator - (C x) {return C(r-x.r,i-x.i);}
	C operator * (C x) {return C(r*x.r-i*x.i,r*x.i+i*x.r);}
}A[N],B[N],w[N];

void FFT(C *a,int n) {
	for (int i=0;i<n;i++)
		if (i<rev[i]) swap(a[i],a[rev[i]]);
	for (int t=n>>1,d=1;d<n;d<<=1,t>>=1) {
		for (int i=0;i<n;i+=(d<<1)) {
			for (int j=0;j<d;j++) {
				C x=a[i+j],y=w[t*j]*a[i+j+d];
				a[i+j]=x+y; a[i+j+d]=x-y;
			}
		}
	}
}

void Solve(int l,int r) {
	if (l==r) {
		ans[0]+=1LL*a[l]*b[r];
		return;
	}
	int mid=(l+r)>>1;
	
	int n=mid-l,m=r-mid-1,limit=1,L=0;
	while (limit<=n+m+2) limit<<=1,++L;
	for (int i=0;i<limit;i++) {
		w[i]=C(cos(2*i*pi/limit),sin(2*i*pi/limit));
		rev[i]=(rev[i>>1]>>1)|((i&1)<<L-1);
	}

	for (int i=0;i<limit;i++) A[i]=B[i]=C(0,0);
	for (int i=0;i<=n;i++) A[i]=C(a[i+l],0);
	for (int i=0;i<=m;i++) B[i]=C(b[i+mid+1],0);
	FFT(A,limit); FFT(B,limit);
	for (int i=0;i<limit;i++) {
		A[i]=A[i]*B[i];
		w[i].i=-w[i].i;
	}
	FFT(A,limit);
	for(int i=0;i<limit;i++) A[i].r/=limit;
	for (int i=0;i<limit;i++) ans[i+l+mid+1]+=(LL)(A[i].r+0.5);

	for (int i=0;i<limit;i++) A[i]=B[i]=C(0,0);
	swap(n,m);
	for (int i=0;i<=n;i++) A[i]=C(a[i+mid+1],0);
	for (int i=0;i<=m;i++) B[m-i]=C(b[i+l],0);
	FFT(A,limit); FFT(B,limit);
	for (int i=0;i<limit;i++) {
		A[i]=A[i]*B[i];
		w[i].i=-w[i].i;
	}
	FFT(A,limit);
	for (int i=0;i<limit;i++) A[i].r/=limit;
	for (int i=0;i<limit;i++) ans[i+1]+=(LL)(A[i].r+0.5);

	Solve(l,mid); Solve(mid+1,r);
}

void doit() {
	scanf("%d%d%d",&n,&m,&q);
	memset(ans,0,sizeof(ans));
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	for (int i=0;i<n;i++) {
		int x; scanf("%d",&x); a[x]++;
	}
	for (int i=0;i<m;i++) {
		int x; scanf("%d",&x); b[x]++;
	}
	Solve(0,50000);
	while (q--) {
		int x; scanf("%d",&x);
		printf("%lld\n",ans[x]);
	}
}

int main() {
	int T; scanf("%d",&T);
	while (T--) doit();
	return 0;
}