首页 > 其他 > 详细

3527: [Zjoi2014]力 - BZOJ

时间:2014-06-27 12:10:13      阅读:424      评论:0      收藏:0      [点我收藏+]

题目大意:给出n个数qi,定义 Fj为

      bubuko.com,布布扣

    令 Ei=Fi/qi,求Ei。

 

看了很久题解,终于有些眉目,因为知道要用FFT,所以思路就很直了

其实我们就是要±1/(j-i)^2 ( i-j大于0时为正,小于0时为负 ) 和 qi 的乘积要算到j这个位置上,这个满足卷积,所以用FFT优化,但是j-i有负数,所以我们就加上一个n

于是设pi={

i>n,1/(i-n)^2

i<n,-1/(n-i)^2

其他,0

}

然后就套FFT模板就行了

 

bubuko.com,布布扣
 1 const
 2     maxn=800100;
 3 type
 4     cp=record
 5         x,y:double;
 6     end;
 7     arr=array[0..maxn]of cp;
 8 var
 9     a,b,w,tt:arr;
10     n,m:longint;
11 
12 operator -(a,b:cp)c:cp;
13 begin
14     c.x:=a.x-b.x;
15     c.y:=a.y-b.y;
16 end;
17 
18 operator +(a,b:cp)c:cp;
19 begin
20     c.x:=a.x+b.x;
21     c.y:=a.y+b.y;
22 end;
23 
24 operator *(a,b:cp)c:cp;
25 begin
26     c.x:=a.x*b.x-a.y*b.y;
27     c.y:=a.x*b.y+a.y*b.x;
28 end;
29 
30 procedure dft(var a:arr;s,t:longint);
31 var
32     i,p:longint;
33     wt:cp;
34 begin
35     if n>>t=1 then exit;
36     dft(a,s,t+1);dft(a,s+1<<t,t+1);
37     for i:=0 to n>>t>>1-1 do
38         begin
39             p:=i<<t<<1+s;
40             wt:=w[i<<t]*a[p+1<<t];
41             tt[i]:=a[p]+wt;
42             tt[i+n>>t>>1]:=a[p]-wt;
43         end;
44     for i:=0 to n>>t-1 do
45         a[s+i<<t]:=tt[i];
46 end;
47 
48 procedure main;
49 var
50     i:longint;
51 begin
52     read(m);
53     for i:=0 to m-1 do read(a[i].x);
54     for i:=1 to m-1 do b[i].x:=-1/(m-i)/(m-i);
55     for i:=m+1 to m<<1-1 do b[i].x:=1/(i-m)/(i-m);
56     n:=1;
57     while n<m<<1 do n:=n<<1;
58     for i:=0 to n-1 do w[i].x:=cos(pi*2*i/n);
59     for i:=0 to n-1 do w[i].y:=sin(pi*2*i/n);
60     dft(a,0,0);dft(b,0,0);
61     for i:=0 to n-1 do a[i]:=a[i]*b[i];
62     for i:=0 to n-1 do w[i].y:=-w[i].y;
63     dft(a,0,0);
64     for i:=m to m<<1-1 do writeln(a[i].x/n:0:3);
65 end;
66 
67 begin
68     main;
69 end.
View Code

 

 

 

3527: [Zjoi2014]力 - BZOJ,布布扣,bubuko.com

3527: [Zjoi2014]力 - BZOJ

原文:http://www.cnblogs.com/Randolph87/p/3805430.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!