计数好题。
题意：给定简单无向图 \(G=(V,E),|V|=n,|E|=m\)，有 \(n\leq 16,m\leq {n\choose 2}\)，求所有为基环树的子图的权值之和。一个基环树的权值定义为 \(2^w\)，其中 \(w\) 是非叶子节点的个数。
用这篇博客提到的最小元状压 DP 的技巧，我们可以轻松地在 \(O(2^n n^2)\) 的时间内求出一个点子集 \(S\) 成为环的方案数 \(cyc_S\)。由于我们钦定最小元是环起点，两个方向分别被 DP 了一次，所以答案记得 \(\div 2\)。需要注意仅有两个点的不算环！
我们现在先考虑不带权值计算一个点子集成为基环树的方案数，设其为 \(dp_S\)。一个暴力的想法是枚举 \(T\subset S\) 将 \(T\) 作为环缩成一个点跑矩阵树，复杂度 \(O(3^n n^3)\)，可以拿 30 分。
我们得到了 \(dp_S\) 如何计算带权值的方案呢？由于权值跟叶子数量有关，一个经典套路就是钦定一些叶子上容斥。钦定 \(T\subset S\) 必须当叶子，\(S/T\) 部分随便取一颗基环树，那么 \(S/T,T\) 间连边方案数就是 \(T\) 中的点在 \(S/T\) 中的度数乘积，不妨记为 \(\text{cross}(T,S/T)=\)，还有对叶子的 \((-1)^{|T|}\) 的容斥系数。那么有：
如果能更快地求 \(dp_{P}\)，那么后面的部分就可以在 \(O(2^n n)\) 的时间内解决。
接下来有两种方式求 \(dp\) 数组。
继续对叶子容斥
我们不妨设 \(f_{S,T}\) 表示点集为 \(S\)，叶子点集为 \(T\) 的基环树方案数。然后依然考虑钦定部分叶子。
设 \(F_{S,T}=\sum_{T'\supset T} f_{S,T'}\)，相当于算钦定 \(T\) 集合的方案数，\(\text{IFWT}\)（高维差分）回去就是 \(f_{S,T}=\sum_{T'\supset T} F_{S,T'}(-1)^{|T'/T|}\)。
注意到 \(dp_S=\sum_{T\subset S} f_{S,T}=F_{S,\emptyset}\)，以及 \(cyc_S=f_{S,\emptyset}=\sum_{T\subset S} F_{S,T}(-1)^{|T|}\)。只需要算出所有 \(T\) 非空的 \(F_{S,T}\) 就可以算出 \(dp_{S}\)。
而 \(T\) 若非空，我们根据容斥的组合意义容易导出：\(F_{S,T}=\text{cross}(T,S/T) dp_{S/T}\)。
带入上述式子解出 \(dp_S\)，我们有：
可以在 \(O(3^n)\) 的时间内愉快地计算。
注意为了递推 \(\text{cross}\) 函数，我们需要枚举 \(S/T\) 然后刷表。
#include <cstdio>
#include <vector>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int P=998244353;
typedef long long ll;
int path[1<<16][16];
int cyc[1<<16],adj[16];
int n,m,msk;
int pw[17],coe[1<<16],sum[1<<16],f[16],res;
void inc(int &x,int v){if((x+=v)>=P) x-=P;}
void dec(int &x,int v){if((x-=v)<0) x+=P;}
int stk[1<<16],tp;
int main(){
n=read();m=read();msk=(1<<n)-1;
for(int i=0;i<m;++i){
int u=read()-1,v=read()-1;
adj[u]|=(1<<v);
adj[v]|=(1<<u);
}
for(int i=0;i<n;++i) path[1<<i][i]=1;
pw[0]=1;
for(int i=1;i<=n;++i) inc(pw[i]=pw[i-1],pw[i-1]);
for(int s=1;s<(1<<n);++s){
int lb=__builtin_ctz(s);
for(int i=lb;i<n;++i){
if(!path[s][i]) continue;
for(int j=lb+1;j<n;++j){
if(s>>j&1) continue;
if(adj[i]>>j&1) inc(path[s|(1<<j)][j],path[s][i]);
}
}
}
for(int s=1;s<(1<<n);++s){
int lb=__builtin_ctz(s);
for(int i=lb+1;i<n;++i)
if(adj[i]>>lb&1) inc(cyc[s],path[s][i]);
if(cyc[s]&1) cyc[s]+=P;
cyc[s]>>=1;
if(__builtin_popcount(s)<=2u) cyc[s]=0;
}
sum[0]=1;
for(int s=0;s<(1<<n);++s){
if(!cyc[s]) continue;
int tt=(ll)pw[__builtin_popcount(s)]*cyc[s]%P;
for(int i=0;i<n;++i)
if(~s>>i&1)
tt=(ll)(P+1-(f[i]=__builtin_popcount(adj[i]&s)))*tt%P;
for(int dlt=msk^s;dlt;dlt=(dlt-1)&(msk^s)) stk[tp++]=dlt;
while(tp){
int dlt=stk[--tp],lb=__builtin_ctz(dlt);
sum[dlt]=(ll)sum[dlt^(1<<lb)]*f[lb]%P;
if(__builtin_parity(dlt)) inc(cyc[s|dlt],(ll)cyc[s]*sum[dlt]%P);
else dec(cyc[s|dlt],(ll)cyc[s]*sum[dlt]%P);
}
inc(res,tt);
}
printf("%d\n",res);
return 0;
}
给无向图定向
众所周知内向基环树就是每个点出度都为 \(1\) 的弱联通图。计算无向图基环树我们有个方法：给无向图每一个点选择一条邻边定向为出边，考虑所有有向边形成了内向基环森林。
那么我们只需要对于每一个点子集导出子图计算度数的乘积，然后对集合幂级数求个 \(\ln\) 就可以得到一颗内向基环树。
有个小瑕疵，环长为 \(2\) 的内向基环树不能算在答案里。然而当我们把长度为 \(2\) 的环看成一条边，那么相当于在一个生成树上选一条边的方案数。用矩阵树定理计算即可。
时间复杂度为 \(O(2^nn^3)\)，瓶颈在对每个点子集计算矩阵树定理，感觉可能还能优化。
#include <cstdio>
#include <vector>
#include <algorithm>
#pragma GCC optimize(2,3,"Ofast")
#define FWTfor \
for(int i=1;i<(1<<n);i<<=1) \
for(int j=0;j<(1<<n);j+=(i<<1)) \
for(int k=j;k<(j|i);++k)
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int P=998244353;
typedef long long ll;
int path[1<<16][16];
int cyc[1<<16],adj[16],pw[17],inv[17];
int n,m,msk;
void inc(int &x,int v){if((x+=v)>=P) x-=P;}
void dec(int &x,int v){if((x-=v)<0) x+=P;}
int f[17][1<<16],g[17][1<<16];
int ans[1<<16],res;
void FWT(int *arr){FWTfor inc(arr[k|i],arr[k]);}
void IFWT(int *arr){FWTfor dec(arr[k|i],arr[k]);}
int mat[17][17],len;
int qp(int a,int b=P-2){
int res=1;
while(b){
if(b&1) res=(ll)res*a%P;
b>>=1;a=(ll)a*a%P;
}
return res;
}
int det(){
bool fl=0;
int res=1;
for(int i=1;i<=len;++i){
int p=i;
while(p<=len&&!mat[p][i]) ++p;
if(p>len) return 0;
if(p>i){
for(int j=i;j<=len;++j) swap(mat[p][j],mat[i][j]);
fl^=1;
}
res=(ll)res*mat[p][i]%P;
int iv=qp(mat[p][i]);
for(int j=i;j<=len;++j) mat[i][j]=(ll)mat[i][j]*iv%P;
for(int j=i+1;j<=len;++j)
for(int k=len;k>=i;--k)
dec(mat[j][k],(ll)mat[j][i]*mat[i][k]%P);
}
if(fl) return P-res;
return res;
}
int calc(int s){
len=0;
for(int i=0;i<n;++i)
if(s>>i&1){
++len;
mat[len][len]=0;
for(int j=0,t=0;j<n;++j)
if(s>>j&1){
++t;
if(t!=len) mat[len][t]=0;
if(adj[i]>>j&1){++mat[len][len];--mat[len][t];}
}
}
for(int i=1;i<=len;++i)
for(int j=1;j<=len;++j)
if(mat[i][j]<0) mat[i][j]+=P;
--len;
return det();
}
int main(){
n=read();m=read();msk=(1<<n)-1;
for(int i=0;i<m;++i){
int u=read()-1,v=read()-1;
adj[u]|=(1<<v);
adj[v]|=(1<<u);
}
for(int i=0;i<n;++i) path[1<<i][i]=1;
inv[1]=pw[0]=1;
for(int i=1;i<=n;++i) inc(pw[i]=pw[i-1],pw[i-1]);
for(int i=2;i<=n;++i) inv[i]=(ll)inv[P%i]*(P-P/i)%P;
for(int s=1;s<(1<<n);++s){
int lb=__builtin_ctz(s);
for(int i=lb;i<n;++i){
if(!path[s][i]) continue;
for(int j=lb+1;j<n;++j){
if(s>>j&1) continue;
if(adj[i]>>j&1) inc(path[s|(1<<j)][j],path[s][i]);
}
}
}
f[0][0]=1;
for(int s=1;s<(1<<n);++s){
int lb=__builtin_ctz(s),sz=__builtin_popcount(s);
f[sz][s]=1;
for(int i=0;i<n;++i)
if(s>>i&1) f[sz][s]=(ll)__builtin_popcount(adj[i]&s)*f[sz][s]%P;
for(int i=lb+1;i<n;++i)
if(adj[i]>>lb&1) inc(cyc[s],path[s][i]);
if(cyc[s]&1) cyc[s]+=P;
cyc[s]>>=1;
if(sz<=2) cyc[s]=0;
}
for(int i=0;i<=n;++i) FWT(f[i]);
for(int i=1;i<=n;++i){
for(int s=0;s<(1<<n);++s) g[i][s]=f[i][s];
for(int s=0;s<(1<<n);++s){
int tmp=0;
for(int j=1;j<i;++j)
inc(tmp,(ll)j*g[j][s]%P*f[i-j][s]%P);
dec(g[i][s],(ll)inv[i]*tmp%P);
}
}
for(int i=0;i<=n;++i) IFWT(g[i]);
for(int s=1;s<(1<<n);++s){
int sz=__builtin_popcount(s);
int cur=g[sz][s];
dec(cur,(ll)calc(s)*(sz-1)%P);
cur=(ll)cur*pw[sz]%P;
if(cur&1) cur+=P;
cur>>=1;
for(int i=0;i<n;++i)
if(~s>>i&1) cur=(ll)cur*(P+1-__builtin_popcount(adj[i]&s))%P;
inc(res,cur);
}
putchar('\n');
printf("%d\n",res);
return 0;
}
邪典做法
如果我们连 \(n\) 个点 \(n\) 条边的联通图是基环树都不知道，但是我们及其擅长集合幂级数与多项式。
那么我们就可以对于点集和边数设二元集合幂级数 \(F(x,y)=\sum f_{S,e} x^S y^e\)，对二元的占位幂级数求 \(\ln\) 就可以保证联通。
复杂度 \(O(2^nn^4)\)，不知是否可行，也不知能否通过。