題目鏈接

problem

給出兩個長度為n的數列a，b，求一個數列c滿足：$$c[k] = \sum\limits_{i = k} ^ na[i]b[i - k]$$

$n\le 10^5$

solution

長得和卷積很像，觀察一下卷積的形式：$c[k]=\sum\limits_{i=0}^ia[i]b[k-i]$

所以先把b陣列翻轉過來，

然后所求的式子就變成了$c[k]=\sum\limits_{i=k}^na[i]b[n+k-i]$

將$n+k$看做整體，那么形式就和卷積比較像了,令$d[n+k]=c[k]=\sum\limits_{i=k}^na[i]b[n + k - i]$，因為a的$n+1$到$n+k$位置均為0，b的$0$到$k-1$位置均為0.

所以上式也可以寫為$d[n+k]=\sum\limits_{i=0}^{n+k}a[i]b[n+k-i]$，

這樣就可以借助FFT計算了，

注意最后的答案是問c[k]，也就是d[k+n]

code

/*
* @Author: wxyww
* @Date:   2020-01-22 08:04:15
* @Last Modified time: 2020-01-22 08:24:04
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 400010;
const double pi = 3.1415926535897931;
ll read() {
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct complex {
	double x,y;
}A[N],B[N];

complex operator * (const complex &A,const complex &B) {
	return (complex){A.x * B.x - A.y * B.y,A.x * B.y + A.y * B.x};
}
complex operator + (const complex &A,const complex &B) {
	return (complex){A.x + B.x,A.y + B.y};
}
complex operator - (const complex &A,const complex &B) {
	return (complex){A.x - B.x,A.y - B.y};
}
int rev[N];
void FFT(complex *a,int n,int xs) {
	for(int i = 0;i <= n;++i) if(rev[i] > i) swap(a[rev[i]],a[i]);

	for(int m = 2;m <= n;m <<= 1) {
		complex w1 = (complex){cos(2 * pi / m),xs * sin(2 * pi / m)};
		for(int i = 0;i < n;i += m) {
			complex w = (complex){1,0};
			for(int k = 0;k < (m >> 1);++k) {
				complex u = a[i + k];
				complex t = w * a[i + k + (m >> 1)];
				a[i + k] = u + t;
				a[i + k + (m >> 1)] = u - t;
				w = w * w1;
			}
		}
	}

}

int main() {
	int n = read();
	for(int i = 0;i < n;++i) {
		A[i].x = read();B[n - i - 1].x = read();
	}
	--n;
	int tot = 1;
	while(tot <= (n << 1)) tot <<= 1;

	for(int i = 0;i <= tot;++i) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? tot >> 1 : 0);


	FFT(A,tot,1);FFT(B,tot,1);

	for(int i = 0;i <= tot;++i) A[i] = A[i] * B[i];
	FFT(A,tot,-1);
	
	for(int i = 0;i <= n;++i) printf("%d\n",(int)round(A[i + n].x / tot));



	return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/103942.html

標籤：其他

上一篇：PAT乙級1016

下一篇：Asterisk的Hangup命令channel引數如何獲取

bzoj2194 快速傅立葉之二

problem

solution

code