题解：P13843 集合幂级数 exp（非素数模数）

· · 题解

首先我们阅读 Purslane 大神的题解得知，集合幂级数 exp 的意思是 b_S=\sum\limits_{S_1\cup\dots\cup S_k=S,|S_1|+\dots+|S_k|=|S|}\prod\limits_{i=1}^ka_{S_i}。

我们容易写出 b_S=\sum\limits_{T\sube S,\max T=\max S}a_Tb_{S\backslash T}，这是一个半在线子集卷积的形式。

我们按照 |S| 从小到大依次转移，每次做一遍子集卷积，对 a 做 FWT 和 a\times b 做 IFWT 的时候不转移最高位以保证 \max T=\max S。时间复杂度 O(n^32^n)。

注意到子集卷积也是使用的 |S| 来保证集合无交，我们加入一些 |S| 相同的 S，只会对同一层 2^n 个 \operatorname{FWT}(b) 位置产生影响，我们只要加上这些位置的 O(n2^n) 的贡献即可，时间复杂度 O(n^22^n)。

cin>>n;
repn(i,1<<n)cin>>t[i];
repn(i,1<<n)a[i][popc(i)]=t[i];
repn(h,n)repn(i,1<<n)if((i>>h&1)&&(1<<h+1)<i)rep(j,0,n)a[i][j]+=a[i-(1<<h)][j];
rep(c,1,n){
  repn(i,1<<n)w[i]=f[i][c];
  repn(h,n)repn(i,1<<n)if((i>>h&1)&&(1<<h+1)<i)w[i]-=w[i-(1<<h)];
  repn(i,1<<n)if(popc(i)==c)e[i]=w[i]+=t[i];
  repn(h,n)repn(i,1<<n)if(i>>h&1)w[i]+=w[i-(1<<h)];
  repn(i,1<<n)rep(j,1,n-c)f[i][j+c]+=w[i]*a[i][j];
}
e[0]=1;repn(i,1<<n)cout<<e[i]<<' ';cout<<'\n';

同理，本算法也会对集合幂级数 ln 表示支持。作为 exp 的逆运算，显然有 b_S=a_S-\sum\limits_{T\sub S,\max T=\max S}b_Ta_{S\backslash T}，做法几乎一样。

cin>>n;
repn(i,1<<n)cin>>t[i];
repn(i,1<<n)a[i][popc(i)]=t[i];
repn(h,n)repn(i,1<<n)if(i>>h&1)rep(j,0,n)a[i][j]+=a[i-(1<<h)][j];
rep(c,1,n){
  repn(i,1<<n)w[i]=f[i][c];
  repn(h,n)repn(i,1<<n)if((i>>h&1)&&(1<<h+1)<i)w[i]-=w[i-(1<<h)];
  repn(i,1<<n)if(popc(i)==c)e[i]=w[i]=t[i]-w[i];
  repn(h,n)repn(i,1<<n)if((i>>h&1)&&(1<<h+1)<i)w[i]+=w[i-(1<<h)];
  repn(i,1<<n)rep(j,1,n-c)f[i][j+c]+=w[i]*a[i][j];
}
repn(i,1<<n)cout<<e[i]<<' ';cout<<'\n';