3527: [Zjoi2014]力 - BZOJ

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

      3527: [Zjoi2014]力 - BZOJ

令 Ei=Fi/qi,求Ei。

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

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

于是设pi={

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

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

其他,0

}

然后就套FFT模板就行了

 const
maxn=;
type
cp=record
x,y:double;
end;
arr=array[..maxn]of cp;
var
a,b,w,tt:arr;
n,m:longint; operator -(a,b:cp)c:cp;
begin
c.x:=a.x-b.x;
c.y:=a.y-b.y;
end; operator +(a,b:cp)c:cp;
begin
c.x:=a.x+b.x;
c.y:=a.y+b.y;
end; operator *(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; procedure dft(var a:arr;s,t:longint);
var
i,p:longint;
wt:cp;
begin
if n>>t= then exit;
dft(a,s,t+);dft(a,s+<<t,t+);
for i:= to n>>t>>- do
begin
p:=i<<t<<+s;
wt:=w[i<<t]*a[p+<<t];
tt[i]:=a[p]+wt;
tt[i+n>>t>>]:=a[p]-wt;
end;
for i:= to n>>t- do
a[s+i<<t]:=tt[i];
end; procedure main;
var
i:longint;
begin
read(m);
for i:= to m- do read(a[i].x);
for i:= to m- do b[i].x:=-/(m-i)/(m-i);
for i:=m+ to m<<- do b[i].x:=/(i-m)/(i-m);
n:=;
while n<m<< do n:=n<<;
for i:= to n- do w[i].x:=cos(pi**i/n);
for i:= to n- do w[i].y:=sin(pi**i/n);
dft(a,,);dft(b,,);
for i:= to n- do a[i]:=a[i]*b[i];
for i:= to n- do w[i].y:=-w[i].y;
dft(a,,);
for i:=m to m<<- do writeln(a[i].x/n::);
end; begin
main;
end.
上一篇:3.2 配置构建Angular应用——简单的笔记存储应用


下一篇:error C2664: “LoadLibraryW”: 不能将参数 1 从“const char *”转换为“LPCWSTR”