【题解】P3338 [ZJOI2014]力()

题目描述

给出 \(n\) 个数 \(q_1,q_2, \dots q_n\)，定义

对 \(1 \leq i \leq n\)，求 \(E_i\) 的值。
\(1\leq n\leq 10^5\)

题解

对于乘积形式的式子计算，数据范围 \(10^5\)，应该想到 \(FFT\) 加速。于是开始推式子。
首先\(E_i=\frac{F_j}{q_i}=\sum\limits_{i = 1}^{j – 1} \frac{q_i}{(i – j)^2}~-~\sum\limits_{i = j + 1}^{n} \frac{q_i}{(i – j)^2}\)。
令 \(f(i)=q_i\),\(g(i)=\frac{1}{i^2}\)，于是原式为\(E_i=\sum\limits_{i=1}^{j-1}f(i)\times g(j-i)-\sum\limits_{i = j + 1}^{n}f(i)\times g(i-j)\)。
左边已经是一个卷积的形式了，来看看右边。
卷积形式是从零开始的，我们要尽量将式子化成卷积。
于是更改求和为：\(\sum\limits_{i=0}^{n-j}f(j+i)\times g(i)\)。
接下来是一个经典套路，可以将式子翻转使得\(f'(i)=f(n-i)\)，得到\(\sum\limits_{i=0}^{n-j}f'((n-j)-i)\times g(i)\)
两者都是卷积形式，fft$加速一下即可。
小结：

  • fft加速乘法卷积
  • 乘号两边同加减的可以翻转式子
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
	int f=1,j=0;
	char w=getchar();
	while(!isdigit(w)){
		if(w=='-')f=-1;
		w=getchar(); 
	}
	while(isdigit(w)){
		j=j*10+w-'0';
		w=getchar();
	}
	return f*j;
}
const int N=400010;
const double pai=acos(-1);
int n,rev[N];
struct cp{
	double x,y;
	cp (double xx=0,double yy=0){x=xx,y=yy;}
	cp operator +(cp a){return cp(x+a.x,y+a.y);}
	cp operator -(cp a){return cp(x-a.x,y-a.y);}
	cp operator *(cp a){return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
}a[N],b[N],c[N];
void fft(cp *f,int n,int flg){
	for(int i=0;i<n;i++)if(i<rev[i])swap(f[i],f[rev[i]]);
	for(int p=2;p<=n;p<<=1){
		int len=p>>1;
		cp tg(cos(2*pai/p),flg*sin(2*pai/p));
		for(int k=0;k<n;k+=p){
			cp buf(1,0);
			for(int l=k;l<k+len;l++){
				cp tt=buf*f[len+l];
				f[len+l]=f[l]-tt;
				f[l]=f[l]+tt;
				buf=buf*tg;
			}
		}
	}
	if(flg==-1)for(int i=0;i<n;i++)f[i].x/=n;
	return ;
}
signed main(){
	n=rd();
	for(int i=1;i<=n;i++){
		scanf("%lf",&a[i].x),c[n-i].x=a[i].x;
		b[i].x=1.0/i/i;
	}
	int lim=1,L=0;
	while(lim<=(n<<1))lim<<=1,L++;
	for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
	fft(a,lim,1),fft(b,lim,1),fft(c,lim,1);
	for(int i=0;i<lim;i++)a[i]=a[i]*b[i],c[i]=c[i]*b[i];
	fft(a,lim,-1),fft(c,lim,-1);
	for(int i=1;i<=n;i++)printf("%.3lf\n",a[i].x-c[n-i].x);
	return 0;
}
————————

题目描述

给出 \(n\) 个数 \(q_1,q_2, \dots q_n\)，定义

对 \(1 \leq i \leq n\)，求 \(E_i\) 的值。
\(1\leq n\leq 10^5\)

题解

对于乘积形式的式子计算，数据范围 \(10^5\)，应该想到 \(FFT\) 加速。于是开始推式子。
首先\(E_i=\frac{F_j}{q_i}=\sum\limits_{i = 1}^{j – 1} \frac{q_i}{(i – j)^2}~-~\sum\limits_{i = j + 1}^{n} \frac{q_i}{(i – j)^2}\)。
令 \(f(i)=q_i\),\(g(i)=\frac{1}{i^2}\)，于是原式为\(E_i=\sum\limits_{i=1}^{j-1}f(i)\times g(j-i)-\sum\limits_{i = j + 1}^{n}f(i)\times g(i-j)\)。
左边已经是一个卷积的形式了，来看看右边。
卷积形式是从零开始的，我们要尽量将式子化成卷积。
于是更改求和为：\(\sum\limits_{i=0}^{n-j}f(j+i)\times g(i)\)。
接下来是一个经典套路，可以将式子翻转使得\(f'(i)=f(n-i)\)，得到\(\sum\limits_{i=0}^{n-j}f'((n-j)-i)\times g(i)\)
两者都是卷积形式，fft$加速一下即可。
小结：

  • fft加速乘法卷积
  • 乘号两边同加减的可以翻转式子
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
	int f=1,j=0;
	char w=getchar();
	while(!isdigit(w)){
		if(w=='-')f=-1;
		w=getchar(); 
	}
	while(isdigit(w)){
		j=j*10+w-'0';
		w=getchar();
	}
	return f*j;
}
const int N=400010;
const double pai=acos(-1);
int n,rev[N];
struct cp{
	double x,y;
	cp (double xx=0,double yy=0){x=xx,y=yy;}
	cp operator +(cp a){return cp(x+a.x,y+a.y);}
	cp operator -(cp a){return cp(x-a.x,y-a.y);}
	cp operator *(cp a){return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
}a[N],b[N],c[N];
void fft(cp *f,int n,int flg){
	for(int i=0;i<n;i++)if(i<rev[i])swap(f[i],f[rev[i]]);
	for(int p=2;p<=n;p<<=1){
		int len=p>>1;
		cp tg(cos(2*pai/p),flg*sin(2*pai/p));
		for(int k=0;k<n;k+=p){
			cp buf(1,0);
			for(int l=k;l<k+len;l++){
				cp tt=buf*f[len+l];
				f[len+l]=f[l]-tt;
				f[l]=f[l]+tt;
				buf=buf*tg;
			}
		}
	}
	if(flg==-1)for(int i=0;i<n;i++)f[i].x/=n;
	return ;
}
signed main(){
	n=rd();
	for(int i=1;i<=n;i++){
		scanf("%lf",&a[i].x),c[n-i].x=a[i].x;
		b[i].x=1.0/i/i;
	}
	int lim=1,L=0;
	while(lim<=(n<<1))lim<<=1,L++;
	for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
	fft(a,lim,1),fft(b,lim,1),fft(c,lim,1);
	for(int i=0;i<lim;i++)a[i]=a[i]*b[i],c[i]=c[i]*b[i];
	fft(a,lim,-1),fft(c,lim,-1);
	for(int i=1;i<=n;i++)printf("%.3lf\n",a[i].x-c[n-i].x);
	return 0;
}