Warning: session_start(): open(/tmp/sess_b81868741f4a3f6223d6430e2c327990, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== DFT ======
作用：把一个多项式 $f(x)$ 转化成点值表示 $\{(x_0,f(x_0)),(x_1,f(x_1)),...,(x_n,f(x_n))\}$ 的形式。
推导过程：
记 $\omega_k^n=e^{\frac{2k\pi}{n}}$
若 $f(x)=\sum_{i=0}^{n-1}a_ix^i$
将 $f(x)$ 按奇偶次拆开 $f(x)=(a_0+a_2x^2+...+a_{n-2}x^{n-2})+x(a_1+a_3x^2+...+a_{n-1}x^{n-2})=f_1(x^2)+xf_2(x^2)$
其中 $f_1(x)=a_0+a_2x+a_4x^4+...+a_{n-2}x^{\frac{n}{2}-1},f2(x)=a_1+a_3x+...+a_{n-1}x^{\frac{n}{2}-1}$
代入 ${\omega}_k^n$ ，得 $f({\omega}_n^k)=f_1({\omega}_n^{2k})+{\omega}_n^kf_2({\omega}_n^{2k})=f_1({\omega}_{\frac{n}{2}}^k)+{\omega}_n^kf_2({\omega}_{\frac{n}{2}}^k)$
同理 $f({\omega}_n^{k+\frac{n}{2}})=f_1({\omega}_{\frac{n}{2}}^k)-{\omega}_n^kf_2({\omega}_{\frac{n}{2}}^k)$
到这里，可以对这个函数进行分治了，时间复杂度 $O(nlogn)$
代码:
#include
using namespace std;
const double Pi=acos(-1);
void dft(complex *f,int len)
{
if (len==1)return ;//
complex *fl=f,*fr=f+len/2;
for (int k=0;k e(cos(2*Pi/len),sin(2*Pi/len))
complex i(1,0);
for (int k=0;k