题目链接

题解

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

(11−xi)ai (\frac{1}{1-x^i})^{a_i} (1−xi1​)ai​

现在已知了

F(x)=∏i=1∞(11−xi)ai F(x)=\prod_{i=1}^{\infin}(\frac{1}{1-x^i})^{a_i} F(x)=i=1∏∞​(1−xi1​)ai​

要求aia_iai​。

对上式两边取对数

ln⁡F(x)=∑i=1∞−ailn⁡(1−xi) \ln F(x)=\sum_{i=1}^{\infin}-a_i\ln(1-x^i) lnF(x)=i=1∑∞​−ai​ln(1−xi)

对右边泰勒展开

ln⁡F(x)=∑i=1∞ai∑j=1∞xijj \ln F(x)=\sum_{i=1}^{\infin}a_i\sum_{j=1}^{\infin}\frac{x^{ij}}{j} lnF(x)=i=1∑∞​ai​j=1∑∞​jxij​

枚举$T=ij$

ln⁡F(x)=∑T=1∞xT∑d∣TaddT \ln F(x)=\sum_{T=1}^{\infin}x^{T}\sum_{d|T}a_d\frac{d}{T} lnF(x)=T=1∑∞​xTd∣T∑​ad​Td​

即

T[xT]ln⁡F(x)=∑d∣Tadd T[x^T]\ln F(x)=\sum_{d|T}a_dd T[xT]lnF(x)=d∣T∑​ad​d

反演得到

ai=∑d∣iμ(id)d[xd]ln⁡F(x)i a_i=\frac{\sum_{d|i}\mu(\frac{i}{d})d[x^d]\ln F(x)}{i} ai​=i∑d∣i​μ(di​)d[xd]lnF(x)​

因此只要多项式求$\ln$即可得到aia_iai​的值。

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

代码

#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