本文共 2653 字，大约阅读时间需要 8 分钟。

题目链接

题解

令$a_i=0/1$表示元素$i$是否在集合中，那么元素$i$的生成函数为

对上式两边取对数

注意常数优化，可以使用提到的卡常技巧。

代码

#include 
   
    #include 
    
     #include 
     
      #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)char buf[1<<21],*p1=buf,*p2=buf; int read(){
     int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
         if(ch=='-')        {
             f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
         x=x*10+ch-'0';      ch=getchar();    }  return x*f;}int write(int x){
     if(x>9)    {
         write(x/10);    }  putchar(x%10+'0');  return 0;}const int maxn=524288;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 &oth) const  {
       return complex(r+oth.r,i+oth.i);  }  complex operator -(const complex &oth) const  {
       return complex(r-oth.r,i-oth.i);  }  complex operator *(const complex &oth) const  {
       return complex(r*oth.r-i*oth.i,r*oth.i+i*oth.r);  }};inline complex conj(complex x){
     return complex(x.r,-x.i);}const complex hreal=complex(0.5,0);const complex himag=complex(0,-0.5);const complex gimag=complex(0,1);complex w[maxn+10];inline int fft(complex *s,int len){
     for(int i=0,j=0; i
      
       >1;      while((j^=l)
       
        >=1;        }    }  for(int i=1,d=maxn; i
        
         >=1) { for(int j=0; j
         
          >15,a[i]&32767); } for(int i=0; i
          
           >15,b[i]&32767); } for(int i=la; i
           
            >=1; } return res;}int tmp[maxn+10];inline int getinv(int *s,int len,int *res){ if(len==1) { res[0]=quickpow(s[0],mod-2); return 0; } int k=(len+1)/2; getinv(s,k,res); for(int i=0; i
            
             =mod) { g[j]-=mod; } } } int tot=0; for(int i=1; i<=n; ++i) { if(g[i]) { ans[++tot]=i; } } write(tot); putchar('\n'); for(int i=1; i
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/wang3312362136/article/details/86163080 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！