2020-2021 ACM-ICPC, Asia Seoul Regional Contest H. Needle(FFT)

2020-2021 ACM-ICPC, Asia Seoul Regional Contest H. Needle(FFT)

链接

题意：

给出你a,b,c三个序列让求有多少，a[i]+c[i]=2*b[i]

分析：

///迭代版#include using namespace std;const int N = 2e5 + 7;const double PI = acos(-1);int n, m, p;int limit = 1;int res;int l;int r[N];int a[N], b[N], c[N];int sum[N];struct Complex{ double x, y; Complex (double x = 0, double y = 0) : x(x), y(y) {}} A[N], B[N];Complex operator * (Complex J, Complex Q){ //模长相乘，幅度相加 return Complex(J.x * Q.x - J.y * Q.y, J.x * Q.y + J.y * Q.x);}Complex operator + (Complex J, Complex Q){ return Complex(J.x + Q.x, J.y + Q.y);}Complex operator - (Complex J, Complex Q){ return Complex(J.x - Q.x, J.y - Q.y);}void FFT(Complex *A, int type){ for(int i = 0; i < limit; i++) { if(i < r[i]) swap(A[i], A[r[i]]); ///保证不在换过去 } ///从底层开始合并： for(int mid = 1; mid < limit; mid = mid * 2) { ///待合并区间长度的一半，最开始是长度为1的合并，类似倍增的思想 Complex wn(cos(PI / mid), type * sin(PI / mid)); //单位根 for(int len = mid * 2, pos = 0; pos < limit; pos += len) { ///len是区间的长度，pos是当前的位置 Complex w(1, 0); for(int k = 0; k < mid; k++, w = w * wn) { ///只扫左半部分，蝴蝶变换得到有半部分。 Complex x = A[pos + k]; //左半部分 Complex y = w * A[pos + mid + k]; //右半部分 A[pos + k] = x + y;//左加 A[pos + mid + k] = x - y;///右减 } } } if(type == 1) return ; for(int i = 0; i <= limit; i++) { A[i].x = A[i].x / limit; A[i].y = A[i].y / limit;///这个版本没用，加不加没影响，优化的版本必须要加 ///除以我们推出的N。 }}int main(){ int ma, mb, mc; ma = mb = mc = 0; cin >> n; for(int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] += 3e4, ma = max(ma, a[i]),A[a[i]].x++; cin >> m; for(int j = 1; j <= m; j++) scanf("%d", &b[j]), b[j] += 3e4, mb = max(mb, b[j]); cin >> p; for(int i = 1; i <= p; i++) scanf("%d", &c[i]), c[i] += 3e4, mc = max(mc, c[i]),B[c[i]].x++; while(limit <= ma + mc) limit <<= 1, l++;///求出位数l，和2的整数次幂 for(int i = 0; i < limit; i++) { r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));///蝴蝶变换。 } FFT(A, 1); FFT(B, 1); for(int i = 0; i <= limit; ++i) { A[i] = A[i] * B[i]; } FFT(A, -1); for(int i = 0; i <= limit; i++) { sum[i]+=(int)(A[i].x+0.5); } for(int i=1;i<=m;i++){ res+=sum[b[i]*2]; } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。