本文共 8201 字，大约阅读时间需要 27 分钟。
集合幂级数
这个东西是我翻集训队论文看的，由于我太弱只能感性理解了。
类似于生成函数，设 \(U=\{1,2...n\}\)，那么集合幂级数定义为：
\[f=\sum_{S\subseteq U} f_Sx^S\]
集合幂级数的记号 \(x\) 是有意义的，对于一个 \(n\) 维向量 \(x\) 和一个集合 \(S\in U\)，我们定义：
\[x^S=\prod_{i\in S}x_i\]
对于一个 \(n\) 维向量 \(x\) 和一个集合幂级数 \(f\)，定义：
\[f(x)=\sum f_S\cdot x^S\]
可以用这东西来解释莫比乌斯变换（\(\tt FWT\) 正变换）：
\[\hat f_{\vec S}=f(\vec S)=\sum_{i}f_i\cdot\vec S^i\]
其中 \(\vec S\) 根据我们是求的那一位把向量 \(s_i\) 设置成 \(0/1\) 然后带入，所以莫比乌斯变换求出来的是特征向量的点值，它的本质是求值，那么莫比乌斯反演（就是逆变换）的本质是插值，所以 \(\tt FWT\) 中间直接乘是多么地顺理成章！
我们定义集合幂级数的求导为：
\[(cx^S)'=\sum_{v\in S}cx^{S-\{v\}}\]
别问我这个怎么来的，求导比较有用就对了，还是要看一看例题。
游戏机
题目描述
设 \(U=\{1,2...n\}\)，有一个人在玩游戏机，每回合游戏机会随机产生一个 \(U\) 的子集，其中产生子集 \(S\) 的概率为 \(p_S\)，当集合并集为 \(U\) 时游戏结束。问游戏结束的期望回合数。
\(n\leq20\)
解法
把 \(p\) 看成集合幂级数，那么第 \(k\) 回合结束后 \(S\) 集合的概率为集合幂级数 \(p^k\) 的第 \(S\) 项，用集合并卷积来定义乘法。不难得到答案是下面这个东西：
\[[x^U]\sum_{i=1}^\infty k(p^k-p^{k-1})\]
设答案的集合幂级数为 \(f\)，两边做正变换，然后点值就可以直接相乘了：
\[\hat f_S=\sum_{k=1}^\infty k(\hat p_S^k-\hat p_S^{k-1})=-\sum_{k=0}^\infty\hat p_{S}^k\]
\[\hat f_S=\begin{cases}-\frac{1}{1-\hat p_S}&\hat p_S<1\\0&\hat p_S=1\end{cases}\]
然后对 \(\hat f\) 做逆变换即可，时间复杂度 \(O(n2^n)\)
生成子图
题目描述
给你一个 \(n\) 个点的无向图 \(G\)，求联通生成子图的个数对 \(1e9+7\) 取模的结果，\(G\) 的生成子图即包含 \(G\) 中所有结点的子图。
\(n\leq20\)
解法
设 \(f_S\) 为 \(G\) 由结点集 \(S\) 导出的子图的联通生成子图的个数，\(g_S\) 为由结点集 \(S\) 导出的子图生成子图的个数，特别地，令 \(f_\varnothing=g_\varnothing=0\)（要不然不收敛，因为常数项有值就一直卷自己）
\(g\) 好求，\(f\) 难求，这个操作我感觉很像反演之类的，多么高妙的操作！
把 \(f,g\) 看成集合幂级数，用子集卷积定义乘法，则：
\[1+g=\sum_{k\geq0}\frac{f^k}{k!}\]
上式的组合意义是从联通子图里面抽出若干个组成随便的子图，由于同一种图会被卷 \(k!\) 次所以要除掉，因为 \(k=0\) 是可以的所以左边会有常数项 \(1\)，继续推柿子：
\(g\) 是好求的，\(g_S=2^{m_S}\) 也就是导出子图的边数，但是现在一定不要直接用多项式求 \(\ln\) 了！因为集合幂级数不能直接用形式幂级数的方法做的，我们要把它转成形式幂级数再去操作。
先把 \(g\) 转化成集合占位幂级数。
什么是集合占位幂级数，为什么不能直接用集合幂级数呢？
因为本题的乘法是定义的子集卷积，所以要增加一个记号表示 \(pop\_count\)（你回忆下怎么做子集卷积的），集合占位幂级数可以理解成一个二元生成函数，我们定义 \(g\) 的集合占位幂级数 \(G\) 为：
\[G=\sum g_S\cdot z^{|S|}\cdot x^S\]
得到了 \(G\) 之后我们对 \(G\) 做莫比乌斯变换（子集卷积怎么做的你就怎么做就行了），因为我们是把向量 \(\vec S\) 带进去求值了，相当于 \(x^S\) 被我们消掉了，所以 \(G_{\vec S}\) 的这些项挑出来是关于 \(z\) 的 \(n+1\) 次多项式，这个就真的是形式幂级数了，然后对这个形式幂级数求 \(\ln\) 即可。求出来以后再逆变换回去，这样就得到了 \(f\) 的集合占位幂级数，答案就是 \(x\) 的第 \(U\) 项 \(z\) 的第 \(n\) 项。
最后补充一下对于形式幂级数 \(a=\sum_{k\geq 1}a_kz^k\) 求 \(b=\ln(1+a)\) 的递推方法，考虑求导：
\[b_k'+\sum_{i=0}^{k-1}b_i'a_{k-i}=a'_k\]
\[(k+1)b_{k+1}=(k+1)a_{k+1}-\sum_{i=0}^{k-1}(i+1)b_{i+1}a_{k-i}\]
\[b_{k+1}=a_{k+1}-\frac{1}{k+1}\sum_{i=0}^{k-1}(i+1)b_{i+1}a_{k-i}\]
总时间复杂度 \(O(n^22^n)\)，集合幂级数 \(\tt yyds\)！
集合划分计数
题目描述
解法
反而是比较板的题了，设 \(f\) 是集合族对应的集合幂级数，设 \(g\) 为答案对应的集合幂级数，定义本题的乘法子集卷积，那么有：
\[g=\sum_{i=0}^k\frac{f^i}{i}\]
\[g'=f'g-\frac{f^k}{k!}f'\]
我们用先把集合占位幂级数搞出来，再用 \(\tt FWT\) 把它转成形式幂级数，然后就可以为所欲为了，考虑把 \(g\) 这个东西递推出来，我们就考虑单个项的递推：
\[(n+1)g_{n+1}=g'_n=\sum_{i=0}^n(f_i'g_{n-i}-\frac{1}{k}f_{i}^kf_{n-i}')\]
现在的问题变成了求 \(f^k\)，这个东西也可以 \(O(n^2)\) 递推，还是用求导的方法：
把这个东西展开成关于 \(n\) 项系数的等式：
\[\sum_{i=0}^nf_{n-i}h_{i+1}(i+1)=k\sum_{i=0}^nh_{n-i}f_{i+1}(i+1)\]
\[h_{n+1}=\frac{k\sum_{i=0}^n(i+1)h_{n-i}f_{i+1}-\sum_{i=0}^{n-1}f_{n-i}h_{i+1}(i+1)}{(n+1)f_0}\]
但是很明显 \(f_0=0\)，所以我们要把多项式 \(f\) 平移到常数项为有值，那么 \(O(n^22^n)\) 即可解决本题。
搞这么麻烦，多项式快速幂它不香么
CF1034E Little C Loves 3 III
题目描述
解法
小清新题，不过用上面讲的那套理论会会更好理解
考虑 \(p=4\) 有什么特别的地方？这道题直接子集卷积显然是无法通过的，但是我们可以让 \(z=4\)，这样即达到了标记的效果，又省掉了 \(z\) 这一位，所以可以直接 \(or\) 卷积了。
具体来说我们令 \(a_x=s_x\times 4^{cnt(x)},b_x=s_x\times 4^{cnt(x)}\)，卷积的结果除以 \(4^{cnt(x)}\) 就可以得到答案，时间复杂度 \(O(n2^n)\)
#include #include using namespace std; const int M = 1<<21;#define int long longint read(){ int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f;}int n,cnt[M],a[M],b[M];char s[M];void fwt(int *a,int op){ for(int i=1;i <<=1) for(int p=i<<1,j=0;j >1]+(i&1); scanf("%s",s); for(int i=0;i >(2*cnt[i]))&3);}
状压dp
其实主要是个分界线，下面都是状压 \(dp\) 的题。
小结：设计状态
优化状态：合法状态 \(/\) 等价类
CF1342F Make It Ascending
题目描述
解法
\(n\leq 15\) 是一个很神奇的数据范围，通常会和 \(3^n\) 的子集枚举扯上关系。
这道题貌似不好直接操作，考虑反向构造，把若干个数划分到一个集合里面，设 \(dp_{i,p,s}\) 表示划分了 \(i\) 个集合，且第 \(i\) 个集合的基础点是 \(p\)（所有的元素都合并到他），已经使用的元素集合是 \(s\)，第 \(i\) 个集合的最小值。
那么怎么转移呢？使用刷表法，我们枚举原来集合的一个超集 \(s_0\)（复杂度相当于子集枚举），判断 \(sum[s_0]>dp[i][p][s]\) 的时候才能转移，选择 \(s_0\) 编号大于 \(p\) 的第一个点就行了，这里有点贪心的味道因为选取的基础点编号肯定是越小越好，时间复杂度 \(O(n^23^n)\)
为了好写 \(p=p+1\)，输出就还原一下 \(dp\) 路径即可。
#include #include using namespace std;const int M = 16;const int inf = 0x3f3f3f3f;int read(){ int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f;}int T,n,a[M],id[M],dp[M][M][1<<15],sum[1<<15];struct node{ int x,y,z;}fa[M][M][1<<15];void solve(){ for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) for(int k=0;k<(1< dp[i][p][s] && (s0>>p)!=0) { int x=p+1+__builtin_ctz(s0>>p),y=s|s0; dp[i+1][x][y]=min(dp[i+1][x][y],sum[s0]); if(dp[i+1][x][y]==sum[s0]) fa[i+1][x][y]=node{i,p,s}; } } node ans; for(int i=n;i>=1;i--) for(int p=1;p<=n;p++) if(dp[i][p][(1<
CF1326F2 Wise Men
题目描述
解法
第一步就是神来之笔，我们发现相邻两个人认识是 \(1\) 不认识是 \(0\)，这个限制太他妈操蛋了。我们让 \(1\) 表示两个人认识，\(0\) 表示没有限制，算出方案之后再容斥回去即可。
现在问题变成了有若干段 \(1\) 对应的排列计数，就相当于在原图里面选出若干条不相交的链的方案数。设有 \(k\) 条链，第 \(i\) 条链的长度为 \(x_i\)，可以把这个东西看成 \(n\) 的整数拆分，所以情况数只有 \(P(n)=385\)
链的计数可以用集合幂级数来做，我们先用 \(O(n^22^n)\) 预处理长度为 \(i\) 的链的数量，定义乘法为或卷积，直接把长度为 \(x_i\) 的链的集合幂级数卷起来就行了，打表发现卷的次数不会很多。因为只有 \(n\) 个元素，所以最后得到的全集一定是对的，看似还要逆变换，其实对全集这一项用容斥原理逆变换只需要 \(O(2^n)\) 的复杂度。
可以把 \(01\) 串 \(hash\) 到整数拆分序列去就可以得到容斥前的值，发现这个值的意义其实就是对答案做了一次 \(\tt and\) 卷积的正变换，所以我们对它做逆变换就得到了答案。
本题的两个妙妙点：指数级容斥、整数拆分的数量级较小。
#include #include #include #include
CF1152F2 Neko Rules the Catniverse
题目描述
解法
神题，我真的没见过确定顺序的题可以不状压直接搞的，\(\tt OneInDark\) 的解释我认为是最好的。
首先做一个题意转化：找到每个点 \(i\) 之前第一个比他小的点 \(j\)，那么对于这个点合法等价于 \(a_j+m\geq a_i\)，不难发现这是充要条件。
你可能会觉得这个转化是垃圾，但其实它是神来之笔。这道题的突破口是 \(m\leq 4\)，这就提示我们在值域序列上面放原序列的元素，也就是从小到大地往上填。但如果这么做的话就会有一个问题，你怎么知道填的是什么？怎么知道填上去的限制？但是这个题意转化正好适合从小到大填的这个特点，那么我们只需要考虑以前填过的信息即可，这一点是极其重要的。
为了便于理解我们构建出图论模型，\(i\) 连向左边第一个比他小的 \(fa\)，我们在填数的时候确定了值，转移的时候要确定 \(fa\)，我们只需要证明这样和原序列 \(<a>\) 是一一对应的即可，证明 \(<a>\) 能对应到它不难，那怎么证明能对应过去呢？因为某个点的儿子一定是按权值从大到小排列的（顺序就是原序列中的位置），然后这些点的儿子有一定在夹着的区间里面，所以就获得了递归子问题，并且这个递归问题有且只有一个解。
那么只用确定 \(fa\) 即可，这时候就要把前面的东西抛掉去想这个问题。首先可以没有 \(fa\)（相当于 \(fa\) 是超级根），或者是在 \([v-m,v)\) 这个区间里面确定一个合法的 \(fa\)，这样就和状压联系到一起了。说到这里就不难定义出状态 \(dp[i][j][s]\) 表示考虑到值 \(i\)，填入了 \(j\) 个数，后 \(m\) 位置的状态压缩为 \(s\)，转移：
- 不选：
dp[i][j][k]=dp[i-1][j][k>>1]+dp[i-1][j][k>>1|up] - 选：
dp[i][j][k]=dp[i-1][j-1][k>>1]*(1+bit[k>>1])+dp[i-1][j-1][k>>1|up]*(1+bit[k>>1|up])
其中 \(\tt bit\) 表示二进制下 \(1\) 的个数，可以用矩阵加速优化，时间复杂度 \(O(\log n\cdot k\cdot 2^m)\)
最后总结两句吧，这道题真的是神仙，\(n\) 这么大直接定义到状态里面，怎么敢的啊？\(k\) 这么小竟然不状压？还有这个题意转化真是人可以想到的？
这个题我真的搞了大半天，还是要谢谢 \(\tt OneInDark\) 的耐心讲解。
\(dp\) 虽然灵活多变，但还是有原则的，比如说这个题把题意转化到只需要用以前的信息，就可以 \(dp\) 了。
还有真的不要先入为主，觉得哪个思路是不可能的。逻辑主义很重要，比如这题就把 \(n=1e9\) 定义到状态里了（笑），当然我认为最合理的解释是 \(m\) 很小就指引你往这个方向想。
不得不吐槽一句这个题是真的抽象，不知道确定的是什么东西但就是可以 \(dp\)
哎，但是代码却挺好写的。
#include #include const int M = 305;const int MOD = 1e9+7;int read(){ int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f;}int n,m,k,p,up,ans,bit[105];struct Matrix{ int a[M][M]; Matrix() {memset(a,0,sizeof a);} Matrix operator * (const Matrix &b) const { Matrix r; for(int i=0;i<=up;i++) for(int j=0;j<=up;j++) for(int k=0;k<=up;k++) r.a[i][k]=(r.a[i][k]+1ll*a[i][j]*b.a[j][k])%MOD; return r; }}A;Matrix qkpow(Matrix a,int b){ Matrix r; for(int i=0;i<=up;i++) r.a[i][i]=1; while(b>0) { if(b&1) r=r*a; a=a*a; b>>=1; } return r;}int id(int x,int y)//编号函数 { return x*p+y;}signed main(){ n=read();k=read();m=read(); p=1< >1]+(s&1); for(int j=0;j<=k;j++) { for(int s=0;s >1,s2=s1|(1<
转载地址：http://xnozz.baihongyu.com/