集合幂级数
这个东西是我翻集训队论文看的，由于我太弱只能感性理解了。
类似于生成函数，设 \(U=\{1,2...n\}\)，那么集合幂级数定义为：
集合幂级数的记号 \(x\) 是有意义的，对于一个 \(n\) 维向量 \(x\) 和一个集合 \(S\in U\)，我们定义：
对于一个 \(n\) 维向量 \(x\) 和一个集合幂级数 \(f\)，定义：
可以用这东西来解释莫比乌斯变换（\(\tt FWT\) 正变换）：
其中 \(\vec S\) 根据我们是求的那一位把向量 \(s_i\) 设置成 \(0/1\) 然后带入，所以莫比乌斯变换求出来的是特征向量的点值，它的本质是求值，那么莫比乌斯反演（就是逆变换）的本质是插值，所以 \(\tt FWT\) 中间直接乘是多么地顺理成章！
我们定义集合幂级数的求导为：
别问我这个怎么来的，求导比较有用就对了，还是要看一看例题。
游戏机
题目描述
设 \(U=\{1,2...n\}\)，有一个人在玩游戏机，每回合游戏机会随机产生一个 \(U\) 的子集，其中产生子集 \(S\) 的概率为 \(p_S\)，当集合并集为 \(U\) 时游戏结束。问游戏结束的期望回合数。
\(n\leq20\)
解法
把 \(p\) 看成集合幂级数，那么第 \(k\) 回合结束后 \(S\) 集合的概率为集合幂级数 \(p^k\) 的第 \(S\) 项，用集合并卷积来定义乘法。不难得到答案是下面这个东西：
设答案的集合幂级数为 \(f\)，两边做正变换，然后点值就可以直接相乘了：
然后对 \(\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\) 看成集合幂级数，用子集卷积定义乘法，则：
上式的组合意义是从联通子图里面抽出若干个组成随便的子图，由于同一种图会被卷 \(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)\) 的递推方法，考虑求导：
总时间复杂度 \(O(n^22^n)\)，集合幂级数 \(\tt yyds\)！
集合划分计数
题目描述
解法
反而是比较板的题了，设 \(f\) 是集合族对应的集合幂级数，设 \(g\) 为答案对应的集合幂级数，定义本题的乘法子集卷积，那么有：
我们用先把集合占位幂级数搞出来，再用 \(\tt FWT\) 把它转成形式幂级数，然后就可以为所欲为了，考虑把 \(g\) 这个东西递推出来，我们就考虑单个项的递推：
现在的问题变成了求 \(f^k\)，这个东西也可以 \(O(n^2)\) 递推，还是用求导的方法：
把这个东西展开成关于 \(n\) 项系数的等式：
但是很明显 \(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 <cstdio>
#include <iostream>
using namespace std;
const int M = 1<<21;
#define int long long
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,cnt[M],a[M],b[M];char s[M];
void fwt(int *a,int op)
{
for(int i=1;i<n;i<<=1)
for(int p=i<<1,j=0;j<n;j+=p)
for(int k=0;k<i;k++)
{
if(op==1) a[i+j+k]+=a[j+k];
else a[i+j+k]-=a[j+k];
}
}
signed main()
{
n=1<<read();
for(int i=1;i<n;i++)
cnt[i]=cnt[i>>1]+(i&1);
scanf("%s",s);
for(int i=0;i<n;i++)
{
int x=s[i]-\'0\';
a[i]=x<<(2*cnt[i]);
}
scanf("%s",s);
for(int i=0;i<n;i++)
{
int x=s[i]-\'0\';
b[i]=x<<(2*cnt[i]);
}
fwt(a,1),fwt(b,1);
for(int i=0;i<n;i++) a[i]=a[i]*b[i];
fwt(a,-1);
for(int i=0;i<n;i++)
printf("%lld",(a[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 <cstdio>
#include <iostream>
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<<n);k++)
dp[i][j][k]=inf,fa[i][j][k]=node{0,0,0};
dp[0][0][0]=0;
for(int i=0;i<n;i++)
for(int p=0;p<n;p++)
for(int s=0;s<(1<<n);s++)
if(dp[i][p][s]!=inf)
{
int ns=((1<<n)-1)^s;//枚举超集
for(int s0=ns;s0;s0=(s0-1)&ns)
if(sum[s0]>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<<n)-1]<inf)
{
ans=node{i,p,(1<<n)-1};
goto In;
}
In:;
printf("%d\n",n-ans.x);
for(int i=0;i<n;i++) id[i]=i+1;
while(ans.x!=0)
{
node t=fa[ans.x][ans.y][ans.z];
int s=ans.z^t.z;
for(int i=0;i<n;i++)
if((s&(1<<i)) && i!=ans.y-1)
{
printf("%d %d\n",id[i],id[ans.y-1]);
for(int j=i+1;j<n;j++) id[j]--;
}
ans=t;
}
}
signed main()
{
T=read();
while(T--)
{
n=read();
for(int i=0;i<(1<<n);i++) sum[i]=0;
for(int i=0;i<n;i++)
{
a[i]=read();
for(int j=0;j<(1<<n);j++)
if((1<<i)&j) sum[j]+=a[i];
}
solve();
}
}
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 <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int M = 20;
const int N = 1<<M;
#define ull unsigned long long
#define int long long
const ull sd = 371;
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,ans[N],a[M][M],f[N][M],g[M][N],t[M][N],bit[N],st[N];
map<ull,int> mp;
void fwtor(int *a,int n,int op)
{
for(int i=1;i<n;i<<=1)
for(int p=i<<1,j=0;j<n;j+=p)
for(int k=0;k<i;k++)
{
if(op==1) a[i+j+k]=(a[i+j+k]+a[j+k]);
else a[i+j+k]=(a[i+j+k]-a[j+k]);
}
}
void fwtand(int *a,int n,int op)
{
for(int i=1;i<n;i<<=1)
for(int p=i<<1,j=0;j<n;j+=p)
for(int k=0;k<i;k++)
{
if(op==1) a[j+k]+=a[i+j+k];
else a[j+k]-=a[i+j+k];
}
}
void dfs(int u,int la,int now,ull hash)
{
if(u==n)
{
int tmp=0;
for(int i=0;i<(1<<n);i++)
tmp+=t[now][i]*((bit[m^i]&1)?-1:1);
mp[hash]=tmp;
return ;
}
for(int i=la;i<=n-u;i++)
{
for(int j=0;j<(1<<n);j++)
t[now+1][j]=t[now][j]*g[i][j];
dfs(u+i,i,now+1,hash*sd+i);
}
}
signed main()
{
n=read();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%1lld",&a[i][j]);
//处理链
for(int i=0;i<n;i++) f[1<<i][i]=1;
for(int i=0;i<(1<<n);i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
if((i&(1<<j)) && (i&(1<<k))==0 && a[j][k])
f[i|(1<<k)][k]+=f[i][j];
//fwt
memset(g,0,sizeof g);
for(int i=0;i<(1<<n);i++)
{
t[0][i]=1;
if(i) bit[i]=bit[i>>1]+(i&1);
for(int j=0;j<n;j++)
g[bit[i]][i]+=f[i][j];
}
int cnt=0;
for(int i=0;i<=n;i++)
{
fwtor(g[i],(1<<n),1);
}
//整数拆分
m=(1<<n)-1;
dfs(0,1,0,0);
//对应到所有01串上
for(int i=0;i<(1<<n-1);i++)
{
ull hs=0;int top=0,now=1;
for(int j=0;j<n-1;j++)
{
if(i&(1<<j)) now++;
else st[++top]=now,now=1;
}
st[++top]=now;sort(st+1,st+1+top);
for(int j=1;j<=top;j++) hs=hs*sd+st[j];
ans[i]=mp[hs];
}
fwtand(ans,(1<<n-1),-1);
for(int i=0;i<(1<<n-1);i++)
printf("%lld ",ans[i]);
}
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 <cstdio>
#include <cstring>
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<<m;up=id(k,p-1);
for(int s=1;s<p;s++)
bit[s]=bit[s>>1]+(s&1);
for(int j=0;j<=k;j++)
{
for(int s=0;s<p;s++)
{
//不选的转移
int s1=s>>1,s2=s1|(1<<m-1);
if((s&1)==0)
{
A.a[id(j,s)][id(j,s1)]++;
A.a[id(j,s)][id(j,s2)]++;
}
//选择的转移
if(j==0 || (s&1)==0) continue;
A.a[id(j,s)][id(j-1,s1)]+=(1+bit[s1]);
A.a[id(j,s)][id(j-1,s2)]+=(1+bit[s2]);
}
}
A=qkpow(A,n);
for(int i=0;i<p;i++)
ans=(ans+A.a[id(k,i)][id(0,0)])%MOD;
printf("%d\n",ans);
}