BZOJ_3527_[ZJOI2014]_力_(FFT+卷积)
描述
题面:
提交:
http://www.lydsy.com/JudgeOnline/problem.php?id=3527
给出n个数字(q1~qn),定义$$F_i=\sum_{j<i}{q_iq_j\over (i-j)^2}-\sum_{j>i}{q_iq_j\over (i-j)^2}$$
然后设$$E_i={F_i\over q_i}$$
求 \(E_i\)
分析
我们先把式子化简一下$$E_i=\sum_{j<i}{q_j\over (i-j)^2}-\sum_{j>i}{q_j\over (i-j)^2}$$
然后我们令$$f[i]=q_i,g[i]={1\over i^2}$$
然后发现左边好像卷积的形式$$c_i=\sum_{j=0}^ia_jb_{i-j}$$
但是没有 \(j=0\) 和 \(j=i\) 的情况.没关系,我们令 \(f[i]=0 , g[i]=0\) .
这样的话原式\[\sum_{j=1}^{i-1}{q_j\over (i-j)^2}\]就和\[\sum_{j=0}^i{q_j\over (i-j)^2}\]相等了
这样左边就是\[A_i=\sum_{j=0}^if[j]g[i-j]\]的卷积了
我们来看右边,右边也很有成为卷积的潜质啊,可是不满足\(0\le{j}\le{i}\)啊.没关系,我们发现左边的式子和右边的式子正好相反,所以我们考虑"倒过来",
于是就有原式\[\sum_{j=i+1}^nf[j]g[i-j]\]等价于\[\sum_{j=i}^nf[j]g[j-i]\]又等价于\[\sum_{j=0}^{n-i}f[n-j]g[n-j-i]\]
这个变化可以通过换元实现.我们可以设\(f'[x]=f'[n-x]\),这样的话右式就等于$$\sum_{j=0}^{n-i}f'[j]g[n-i-j]$$
这样右边就是$$B_i=\sum_{j=0}^if'[j]g[i-j]$$的卷积了
最后$$E_i=A_i+B_{n-i}$$
开心地FFT吧~
注意:
1.由于数组是从1开始的,预留了\(f[0]与g[0]\)的位置,所以长度应该+1,所以len=2*n-1+1+1=2*n+1.
#include <bits/stdc++.h>
using namespace std; const int maxn=;
const double pi=acos(-1.0);
int n,len;
int rev[maxn];
double f[maxn],f_[maxn],g[maxn],ans[maxn];
struct cp{
double r,i;
cp(double r=,double i=):r(r),i(i){}
cp operator + (const cp &x) const { return cp(r+x.r,i+x.i); }
cp operator - (const cp &x) const { return cp(r-x.r,i-x.i); }
cp operator * (const cp &x) const { return cp(r*x.r-i*x.i,r*x.i+i*x.r); }
}a[maxn],b[maxn],c[maxn],A[maxn];
void brc(int &len){
memset(rev,-,sizeof rev);
int k=,l=;
while(k<len) k<<=, l++;
len=k;
for(int i=;i<len-;i++){
if(rev[i]!=-) continue;
int x=i,y=,m=l;
while(m--) y<<=, y|=(x&), x>>=;
rev[i]=y; rev[y]=i;
}
}
void dft(cp *a,int n,int op){
for(int i=;i<n-;i++) A[rev[i]]=a[i];
for(int i=;i<n-;i++) a[i]=A[i];
for(int m=;m<=n;m<<=){
cp wn(cos(2.0*pi/m*op),sin(2.0*pi/m*op));
for(int i=;i<n;i+=m){
cp w(1.0); int k=m>>;
for(int j=;j<k;j++){
cp u=a[i+j],t=w*a[i+j+k];
a[i+j]=u+t;
a[i+j+k]=u-t;
w=w*wn;
}
}
}
if(op==-)for(int i=;i<n;i++) a[i].r/=n;
}
void fft(double *x,double *y,cp *a,cp* b,cp *c,int n){
for(int i=;i<len;i++) a[i]=cp(x[i]), b[i]=cp(y[i]);
dft(a,n,); dft(b,n,);
for(int i=;i<n;i++) c[i]=a[i]*b[i];
dft(c,n,-);
}
int main(){
scanf("%d",&n); len=*n+;
brc(len);
for(int i=;i<=n;i++) scanf("%lf",&f[i]);
for(int i=;i<=n;i++) g[i]=1.0/i/i;
for(int i=;i<=n;i++) f_[i]=f[n-i];
fft(f,g,a,b,a,len);
for(int i=;i<=n;i++) ans[i]=a[i].r;
fft(f_,g,a,b,a,len);
for(int i=;i<=n;i++) ans[i]-=a[n-i].r;
for(int i=;i<=n;i++) printf("%.3lf\n",ans[i]);
return ;
}
最新文章
- java nio系列文章
- Python通用序列操作
- Lamp源码搭建
- VC++ MFC子对话框建立与关闭
- [2011山东ACM省赛] Sequence (动态规划)
- 【读书笔记《Android游戏编程之从零开始》】9.游戏开发基础(如何快速的进入 Android 游戏开发)
- SpringMVC @RequestBody接收Json对象字符串 demo
- BZOJ 3720 gty的妹子树
- .NET知识点总结一(笔记整合)
- Hadoop基准测试(转载)
- IAR和Keil文件包含路径设置
- UVa1587 盒子
- # .NET切面编程——PostSharp
- 调试利器GDB(下)
- 信息在DNN马尔科夫链结构上的变化
- websocket协议握手详解
- mybatis检测mysql表是否存在
- JAVA基础-栈与堆,static、final修饰符、内部类和Java内存分配
- CF786B Legacy &;&; 线段树优化连边
- IP地址分类以及子网划分