http://192.168.102.138/JudgeOnline/problem.php?cid=1478&pid=2
1.题目思路:1.只考虑“+” :生成函数经典模型(“+”以及最终查询的“和”有多个不同的值)
2.考虑“-”:架设生成函数中的次数可以为负数,那么就跟“+”一样处理就好,但FFT无法处理负数,所以我们考虑把最终查询的和+100002,而每一个次数都+50001,这就意味着负数变成了正数,可以使用FFT,而且不影响最终结果
3.处理条件:因为已经将其转化为一个生成函数(即多项式),那么我们不难发现次数小的一定比次数大的要小,但我们不能枚举每一对的大小关系,为了能用到FFT的时间优势,于是我们考虑分治,比mid小的显然比mid大的要小,如此,就把al~mid 与bmid+1~r 的贡献 和 amid+1~r 与 bl~mid 的贡献相加,然后再分治就做完了
2.知识点:1.生成函数
2.分治确定大小关系
3.通过CDQ分治限制大小关系,从而解决一些有要求的题,满足一些条件
Code:
#include <bits/stdc++.h> using namespace std; const double FI = acos(-1); struct edge { double x; double y; }A[500010],B[500010]; int a[500010],b[500010],inv1[500010]; int n; int T,x,m,Q; int len1,len2; long long ans[500010]; edge operator + (edge &a,edge &b) { return (edge){a.x + b.x,a.y + b.y}; } edge operator - (edge &a,edge &b) { return (edge){a.x - b.x,a.y - b.y}; } edge operator *(const edge &a,const edge &b) { return (edge){a.x * b.x - a.y * b.y,a.x * b.y + a.y * b.x}; } void FFT(edge *a,int leng,int type) { for (int i = 0; i < leng; i++) if(i < inv1[i]) swap(a[i],a[inv1[i]]); for (int i = 1; i < leng; i <<= 1 ) { edge wn = (edge){cos(FI / i),type * sin(FI / i)}; for (int p = i << 1, j = 0; j < leng; j += p) { edge w = (edge){1,0}; for (int k = 0; k < i; k++,w = w * wn) { edge x = a[j + k],y = w * a[i + j + k]; a[j + k] = x + y; a[i + j + k] = x - y; } } } if (type == 1) return; for (int i = 0; i < leng; i++) a[i].x /= leng; } void CDQ(int l,int r) { if (l == r) return; int mid = (l + r) >> 1; int n,L = 0; for (n = 1; n <= r - l + 1; n <<= 1) L++; for (int i = 0; i < n; i++) inv1[i] = (inv1[i >> 1] >> 1) | ((i & 1) << (L - 1)); for (int i = 0; i < n; i++) A[i] = B[i] = (edge){0,0}; for (int i = l; i <= mid; i++) A[i - l].x = a[i]; for (int i = mid + 1; i <= r ; i++) B[i - mid - 1].x = b[i]; FFT(A,n,1); FFT(B,n,1); for (int i = 0; i < n; i++) A[i] = A[i] * B[i]; FFT(A,n,-1); for (int i = 0; i < n; i++) ans[i + mid + 1 + l] += (long long)(A[i].x + 0.5); for (int i = 0; i < n; i++) A[i] = B[i] = (edge){0,0}; for (int i = mid + 1; i <= r; i++) A[i - mid - 1].x = a[i]; for (int i = l; i <= mid; i++) B[mid - i].x = b[i]; FFT(A,n,1); FFT(B,n,1); for (int i = 0; i < n; i++) A[i] = A[i] * B[i]; FFT(A,n,-1); for (int i = 0; i < n; i++) ans[i + 1] += (long long)(A[i].x + 0.5); CDQ(l,mid); CDQ(mid + 1,r); } int main() { scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&Q); memset(ans,0,sizeof(ans)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); len1 = len2 = 0; for (int i = 1; i <= n; i++) { scanf("%d",&x); a[x]++; len1 = max(len1,x); } for (int i = 1; i <= m; i++) { scanf("%d",&x); b[x]++; len2 = max(len2,x); } for (int i = 1; i <= len1 && i <= len2; i++) ans[0] += 1ll * a[i] * b[i]; CDQ(0,max(len1,len2)); for (int i = 1; i <= Q; i++) scanf("%d",&x),printf("%lld\n",ans[x]); } return 0; }