题目链接

思路

FFT半裸题了。

如果一个多项式有

xi x i $x^i$ 项，另一个多项式有

xj x j $x^j$ 项，那么相乘后的多项式就一定有

xi+j x i + j $x^{i+j}$ 项。

那么如果读入一个数

i i $i$ ，那么多项式

x^{i}

$x^i$ 项就赋值为

1 1 <script type="math/tex" id="MathJax-Element-295">1</script>。

最后把多项式平方，得出多项式次数为哪些时，系数有值，说明这个次数能被凑出来。

代码

#include 
   
    #include 
    
     #include 
     
      const int maxn=200000;const double pi=acos(-1);struct complex{  double r,i;  complex(double r_=0,double i_=0)  {    r=r_;    i=i_;  }  complex operator +(const complex &other) const  {    return complex(r+other.r,i+other.i);  }  complex operator -(const complex &other) const  {    return complex(r-other.r,i-other.i);  }  complex operator *(const complex &other) const  {    return complex(r*other.r-i*other.i,r*other.i+i*other.r);  }};complex a[maxn<<2];int rev[maxn<<2],n,m,ans;int fft(complex* ar,int len,int op){  for(register int i=0; i
      
       >1); ++k)            {              complex x=ar[j+k],y=w*ar[j+k+(i>>1)];              ar[j+k]=x+y;              ar[j+k+(i>>1)]=x-y;              w=w*wn;            }        }    }  if(op==-1)    {      for(register int i=0; i
       
        >1]>>1)|((i&1)<<(l-1));    }  return 0;}int main(){  scanf("%d",&n);  for(register int i=1; i<=n; ++i)    {      int w;      scanf("%d",&w);      a[w].r=1;    }  a[0]=1;  calc(maxn<<1);  fft(a,m,1);  for(register int i=0; i
        
         0) { ++ans; } } printf("%d\n",ans); return 0;}

上一篇：[2018省队模拟]简单模拟

下一篇：浅谈算法——从多项式乘法到FFT

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目链接

思路

代码

发表评论

最新留言

关于作者

推荐文章