专栏文章

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

mmin_inf
P13843题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio36qdh
此快照首次捕获于
2025/12/02 12:37
3 个月前
此快照最后确认于
2025/12/02 12:37
3 个月前
查看原文
首先我们阅读 Purslane 大神的题解得知，集合幂级数 exp 的意思是 bS=∑S1∪⋯∪Sk=S,∣S1∣+⋯+∣Sk∣=∣S∣∏i=1kaSib_S=\sum\limits_{S_1\cup\dots\cup S_k=S,|S_1|+\dots+|S_k|=|S|}\prod\limits_{i=1}^ka_{S_i}。
我们容易写出 bS=∑T⊆S,max⁡T=max⁡SaTbS\Tb_S=\sum\limits_{T\sube S,\max T=\max S}a_Tb_{S\backslash T}，这是一个半在线子集卷积的形式。
我们按照 ∣S∣|S| 从小到大依次转移，每次做一遍子集卷积，对 aa 做 FWT 和 a×ba\times b 做 IFWT 的时候不转移最高位以保证 max⁡T=max⁡S\max T=\max S。时间复杂度 O(n32n)O(n^32^n)。
注意到子集卷积也是使用的 ∣S∣|S| 来保证集合无交，我们加入一些 ∣S∣|S| 相同的 SS，只会对同一层 2n2^n 个 FWT⁡(b)\operatorname{FWT}(b) 位置产生影响，我们只要加上这些位置的 O(n2n)O(n2^n) 的贡献即可，时间复杂度 O(n22n)O(n^22^n)。
CPP
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 的逆运算，显然有 bS=aS−∑T⊂S,max⁡T=max⁡SbTaS\Tb_S=a_S-\sum\limits_{T\sub S,\max T=\max S}b_Ta_{S\backslash T}，做法几乎一样。
CPP
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';

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...