[做题笔记] 浅谈状压dp在图计数问题上的应用
无向图计数
题目描述
点此看题
有一个 \(n\) 个点 \(m\) 条边的无向图，对于每个 \(k\) 求出有多少种保留边的方案使得 \(1\) 能到 \(k\)
\(n\leq 17,m\leq {n\choose 2}\)
解法
设 \(dp[s]\) 表示 \(1\) 能到集合 \(s\)，只考虑集合 \(s\) 中的边的方案数，转移考虑总方案减去不合法的方案，不合法的方案可以枚举一个 \(s\) 的真子集 \(t\)，那么 \(s\oplus t\) 和 \(t\) 之间不能有边，\(s\oplus t\) 边任意，设 \(cnt[s]\) 表示 \(2\) 的 \(s\) 内部边数次方：
\[dp[s]=cnt[s]-\sum_{t\subset s}dp[t]\times cnt[s-t] \]可以用 \(\tt FWT\) 优化（用类似子集卷积的方案，按照大小分类），时间复杂度 \(O(3^n)/O(2^nn^2)\)
总结
正难则反是考虑连通性问题的一类重要方法。
#pragma GCC optimize(2)
#include
const int M = 18;
const int MOD = 998244353;
#define int long long
int read()
{
int x=0,flag=1;char c;
while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*flag;
}
int n,m,g[M][M],ans[M],dp[1< 强连通计数
题目描述
点此看题
解法
这个题很好，有向图计数问题可以转 \(\tt DAG\) 计数，因为那东西已经有一套成熟的计算方法了。
设 \(f[s]\) 表示只考虑集合 \(s\) 的点和它们的边的方案数，还是总数减去不合法的方案数，计算不合法的方案数直接转 \(\tt DAG\) 计数，也就是考虑不合法的方案意味着缩点之后构成了 \(\tt DAG\)，并且点数大于 \(1\)
那么我们对入度为 \(0\) 的点容斥，设 \(g[s]\) 是钦定集合 \(s\) 中的点入度为 \(0\) 的方案数，转移：
\[g[s]=-\sum_{t\subset s}g[t]\times f[s-t] \]也就是每次新添加一个入度为 \(0\) 的强连通块，为了不算重需要保证 \(t\) 中包含 \(\tt lowbit\) 这一位的点。
设 \(sn[s]\) 表示集合 \(i\) 连向集合 \(s\) 的边，这个每次 \(dp\) 的时候需要在线处理出来，设 \(s[i]\) 表示集合 \(i\) 内部的边数，那么钦定一个子集入度为 \(0\) 来转移，其他的边可以随便选：
\[f[i]=2^{s[i]}-\sum_{j\subseteq i} g[j]\times 2^{s[i]-sn[j]} \]其中 \(j\) 枚举的是非空子集，转移完 \(f\) 之后让 \(g[i]\leftarrow g[i]+f[i]\) 当作一个小的初始化，时间复杂度 \(O(3^n)\)
#include
const int M = 15;
const int N = 1<<15;
const int MOD = 1e9+7;
#define int long long
int read()
{
int x=0,flag=1;char c;
while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*flag;
}
int n,m,in[N],out[N],pw[N],cnt[N],s[N],sn[M],f[N],g[N];
void calc(int nw,int i)
{
int to=(nw-1)&i;
if(to) calc(to,i);
sn[nw]=sn[nw-(nw&(-nw))]+cnt[in[nw&(-nw)]&i];
//sn[nw]=sn[to]+cnt[in[nw-to]&i]
//what I show above is wrong,think about it
}
signed main()
{
n=read();m=read();pw[0]=1;
for(int i=1;i<=m;i++)
{
int u=read()-1,v=read()-1;
in[1<>1]+(i&1);
for(int i=1;i<(1< 二分图计数
题目描述
点此看题
给一张 \(n\) 个点 \(m\) 条边的无向图，问有多少种保留边的方案使得最后的图是联通二分图。
\(n\le1 7,m\leq{n\choose 2}\)
解法
这题有两个限制，一个是二分图，一个是联通。
考虑分别解决限制，首先考虑集合 \(s\) 是二分图的方案数，显然的思路是枚举一个子集 \(t\)，然后考虑两个集合任意连边，但是这样显然会算重，非连通二分图会被统计多次。
很难去重，但是考虑我们算的方案是具有组合意义的，我们求出的是二分图的染色方案，一个惊为天人的思路是 \(dp\) 二分图的染色方案，最后求出的是连通二分图的染色方案，所以除以 \(2\) 就得到答案了。
设 \(g[s]\) 是集合 \(s\) 的二分图染色方案，\(f[s]\) 是集合 \(s\) 的连通二分图染色方案，然后老正难则反了，我们枚举子集 \(t\)，强制 \(s-t\) 为连通块，为了防止算错我们强制 \(t\) 不包含 \(\tt lowbit\) 那一位：
\[f[s]=g[s]-\sum_t f[s-t]\times g[t] \]预处理集合 \(se[s]\) 表示集合 \(s\) 内部的边数，时间复杂度 \(O(2^nm+3^n)\)
#include
const int N = 1<<17;
const int MOD = 998244353;
const int inv2 = (MOD+1)/2;
#define int long long
int read()
{
int x=0,flag=1;char c;
while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*flag;
}
int n,m,cnt[N],e[N],se[N],g[N],f[N],pw[405];
signed main()
{
n=read();m=read();pw[0]=1;
for(int i=1;i<=m;i++)
{
int u=read()-1,v=read()-1;
e[i]=(1<>1]+(i&1);
for(int i=0;i<(1<