题目：

第一道FFT！

就是把系数转化为2*n个点值，点值相乘一下，再转化回2*n个系数的过程。

转化为点值的过程就是倍增一样，第一步是w_{1,0}，也就是说x都是1，所以一开始2*n个位置上的点值都是原来的系数；然后变成两个一组取w_{2,0}，w_{2,1}的点值，最后变成2*n个分别取w_{2*n,0}，w_{2*n,1}，......，w_{2*n,2*n-1}的点值。过程就是DFT，证明可见上面博客。

从点值转化回系数的方法和DFT差不多，似乎只要把 x 都变成倒数、做一边刚才的就行。变成倒数的方法就是那个Wn方向变成负的，这样 x^k 就是倒着转的，上面那个角标就一直是和原来相反的了。

最后算答案的时候似乎直接把虚数的部分舍弃了。

对于iDFT的证明还有点不明白。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define db doubleusing namespace std;const int N=1e6+5;const db pi=acos(-1.0);int n,m,len,r[N<<2];//<<2! for (n+m)<<1struct cpl{  db x,y;}I,a[N<<2],b[N<<2];cpl operator+ (cpl a,cpl b){
   return (cpl){a.x+b.x,a.y+b.y};}cpl operator- (cpl a,cpl b){
   return (cpl){a.x-b.x,a.y-b.y};}cpl operator* (cpl a,cpl b){
   return (cpl){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
   if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();  return fx?ret:-ret;}void fft(cpl *a,bool fx){  for(int i=0;i
          
           >1; cpl Wn=(cpl){ cos(pi/m),(fx?-1:1)*sin(pi/m) }; for(int i=0;i
           
            >1]>>1)+((i&1)?len>>1:0); fft(a,0); fft(b,0); for(int i=0;i