BZOJ 3527 [ZJOI2014]力

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解

就是把qj除掉,然后可以发现是裸的两个卷积形式,直接上FFT就可以。

这个博客写的非常好,我个人就比较渣了QAQ https://blog.csdn.net/qq_33929112/article/details/54590319

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int maxn = (1<<18) + 5;
const int INF = 1e9;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = (num << 1) + (num << 3) + c - '0';
	return (flag ? -1 : 1) * num;
}
struct comp{
	double x,y;
	comp(double a = 0,double b = 0):x(a),y(b){};
};
comp operator + (comp a,comp b){return comp(a.x + b.x,a.y + b.y);}
comp operator - (comp a,comp b){return comp(a.x - b.x,a.y - b.y);}
comp operator * (comp a,comp b){return comp(a.x*b.x - a.y * b.y,a.x * b.y + a.y * b.x);}
comp conj(comp a){
	return comp(a.x,-a.y);
}
struct FFT{
	int n,rev[maxn];
	void get_inv(int bit){
		n = 1;int k = 0;
        while(n < bit) n <<= 1,k++;
        for(int i = 0;i < n;i++) {
            int t = 0;
            for(int j = 0;j < k;j++) if(i&(1<<j)) t |= (1<<(k-1-j));
            rev[i]=t;
		}
	};
	void dft(comp *a,int flag){
		for(int i = 0;i < n;++i)
			if(i < rev[i])swap(a[i],a[rev[i]]);
		for(int l = 2;l <= n;l <<= 1){
			int m = l >> 1;
			comp wn = comp(cos(2*PI/l),flag * sin(2*PI/l));
			for(comp *p = a;p != a + n;p += l){
				comp w = comp(1,0);
				for(int k = 0;k < m;++k){
					comp t = w * p[k + m];
					p[k + m] = p[k] - t;
					p[k] = p[k] + t;
					w = w * wn;
				}
			}
		}
		if(flag == -1)for(int i = 0;i < n;++i)a[i].x /= n;
	}
}fft;
int n;
comp a[maxn],b[maxn],c[maxn];
int main(){
	n = get_num();
	double x;
	for(int i = 0;i < n;++i)scanf("%lf",&x),a[i].x = b[n-1-i].x = x;
	for(int i = 1;i < n;++i)c[i].x = 1.0 / i / i;
	fft.get_inv(2*n-1);
	fft.dft(a,1);
	fft.dft(b,1);
	fft.dft(c,1);
	for(int i = 0;i < fft.n;++i)a[i] = a[i] * c[i],b[i] = b[i] * c[i];
	fft.dft(a,-1);fft.dft(b,-1);
	for(int i = 0;i < n;++i){
		printf("%lf\n",a[i].x - b[n-1-i].x);
	}
	return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00