注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ3527】【Zjoi2014】【力】  

2014-04-16 15:07:25|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     题目大意:给出n个数qi,定义 Fj为
      【BZOJ3527】【Zjoi2014】【力】 - z55250825 - z55250825
    令 Ei=Fi/qi,求Ei。

   其实这道题就是看到有FFT模板才觉得有必要学一下的...
   所以实际上就是已经知道题解了... = =。
   【BZOJ3527】【Zjoi2014】【力】 - z55250825 - z55250825
  所以问题就是求这两个多项式相乘的系数。
  这里咱卷积不太熟悉,所以咱们来证明一下这个结论显然还是不错的。
  首先咱们设 f(x)(k) 表示f(x)的 第k项的系数(就是 x^k-1 那一项)
  那么首先了解下卷积,如果f,g是一个序列(这指的是其系数构成的序列),那么卷积S也是一个序列
  咱们有:
     S(k)=∑f(x)(i)*g(x)(k-i)
  这个就是卷积,感觉会不会和FFT很熟悉额?
  其实多项式乘法的结果的第K项其实就是 乘上去的两个多项式的 系数的卷积S(k)。
  那么咱们就有卷积定理:
  A 卷 B = DFT^-1(DFT(A)*DFT(B)),其中DFT就是离散化傅里叶变换,DFT^-1即逆向的。
  然后咱们证明 Ej就是 f(x)和g(x)系数的卷积 S(j)
  即证明 ∑f(x)(i)*g(x)(j-i)=Ej=∑qi/(i-j)^2-∑qi/(i-j)^2
  左边弄开来:
  对于S(k),当i=k的时候,g的那一边为n,g(x)(n)=0,为0。
                      当i<k的时候,g的那一边为大于n的,则咱们设的g(x)(n+k-i)>0,而这里的i是<k的qi会算进来。
                      当i>k的时候,g的那一边为小于n的,而咱们设的g(x)(n+k-i)<0,而这里的i是>k的qi会算进来。
                      这些都是符合的。然后咱们还得证明越界的话会发生什么,假设i>n了,它是0,然后i<0,它也是0,所以越界只会使那个变成0,所以这个是正确的,然后实际上咱们只需要 n+1~2n的卷积即可。
                      然后还有系数,g(n+k-i)的系数是 1/(n+k-i-n)^2,突然发现竟然就是 1/(k-i)^2【这里的正确性咱还是有的迷糊...待修改】

 然后弄清楚之后就可以直接上模板了。
 这题的卷积还值得再品味一下。
================================

program bzoj3527;
type cp=record x,y:double;end;
     arr=array[0..1 shl 18]of cp;

var a,b,tt,w:arr;
    wt:cp;
    m,n:longint;

operator *(var a,b:cp)c:cp;
begin c.x:=a.x*b.x-a.y*b.y;c.y:=a.x*b.y+a.y*b.x;end;
operator +(var a,b:cp)c:cp;
begin c.x:=a.x+b.x;c.y:=a.y+b.y;end;
operator -(var a,b:cp)c:cp;
begin c.x:=a.x-b.x;c.y:=a.y-b.y;end;

procedure dft(var a:arr;s,t:longint);
var i,p:longint;
begin
  if n shr t=1 then exit;
  dft(a,s,t+1);
  dft(a,s+(1 shl t),t+1);
  for i:=0 to n shr (t+1)-1 do
   begin
     p:=i shl (t+1)+s;
     wt:=w[i shl t]*a[p+1 shl t];
     tt[i]:=a[p]+wt;
     tt[i+n shr (t+1)]:=a[p]-wt;
   end;
  for i:=0 to n shr t-1 do a[i shl t+s]:=tt[i];
end;

procedure init;
var i:longint;
    ans:double;
begin
  read(n);
  for i:=0 to n-1 do read(a[i].x);
  for i:=0 to n-1 do b[i].x:=(-1.0/(n-i))/(n-i);
  b[n].x:=0;
  for i:=1 to n do b[n+i].x:=(1.0/i)/i;
  m:=1;
  while m<(n shl 1+1) do m:=m shl 1;
  i:=n;n:=m;m:=i;
  for i:=0 to n-1 do w[i].x:=cos(pi*2*i/n);
  for i:=0 to n-1 do w[i].y:=sin(pi*2*i/n);
  dft(a,0,0);dft(b,0,0);
  for i:=0 to n-1 do a[i]:=a[i]*b[i];
  for i:=0 to n-1 do w[i].y:=-w[i].y;
  dft(a,0,0);
  for i:=m to m shl 1-1 do
   begin
     ans:=a[i].x/n;
     writeln(ans:0:3);
   end;
end;

begin
  init;
end.


  评论这张
 
阅读(371)| 评论(6)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017