FFT模版1

题目描述:

现在有类似如下的函数：

f(x)=sin(2*π*p1/n*x+q1)*r1+sin(2*π*p2/n*x+q2)*r2+sin(2*π*p3/n*x+q3)*r3+...+sin(2*π*pm/n*x+qm)*rm。（pi是整数且0<pi<n/2，qi、ri是实数）

已知x=0到n-1的每一个整数时f(x)的值，求f(x)

输入格式:

第1行输入n

第2-n+1行输入n个实数（每行1个），第i个实数表示x=i-1时f(x)的值

输出格式:

输出若干行，第i行一个正整数pi和一个实数ri（无需输出qi）。正整数pi需满足0<p1<p2<p3<...<pm<n/2。会用SPJ检查结果（浮点绝对误差小于1e-4即算正确）。

样例输入:

8
0
2
0
-2
0
2
0
-2

样例输出:

2 2

下载附加文件

提示:

p1=2，q1=0，r1=2。

f(x)=sin(2*π*p1/n*x+q1)*r1=sin(2*π*2/8*x+0)*2=sin(π/2*x)*2

数据范围

保证f(x)存在。

保证n=2^k，k是整数。

小样例中k=3，大样例中k=11

测试数据1中k=11

测试数据2中k=11

测试数据3中k=12

测试数据4中k=13

测试数据5中k=14

 

如果你的程序对于小样例输出的是

1 0
2 2

或

2 2
3 0

那么SPJ会判你AC。

如果你的程序对于小样例输出的是

2 2.0000001

或

2 2
3 0.0000001

那么SPJ也会判你AC。

如果你的程序对于小样例输出的是

2 1
2 1

或

1 0
1 0
2 2

那么SPJ会判你WA

时间限制: 1000ms
空间限制: 256MB

---