是zx2003 的做法。

众所周知内向基环树就是每个点出度都为 \(1\) 的弱联通图。计算无向图基环树我们有个方法：给无向图每一个点选择一条邻边定向为出边，考虑所有有向边形成了内向基环森林。

那么我们只需要对于每一个点子集导出子图计算度数的乘积，然后对集合幂级数求个 \(\ln\) 就可以得到一颗内向基环树。

有个小瑕疵，环长为 \(2\) 的内向基环树不能算在答案里。然而当我们把长度为 \(2\) 的环看成一条边，那么相当于在一个生成树上选一条边的方案数。用矩阵树定理计算即可。

时间复杂度为 \(O(2^nn^3)\)，瓶颈在对每个点子集计算矩阵树定理，感觉可能还能优化。

#include #include #include #pragma GCC optimize(2,3,"Ofast")#define FWTfor \for(int i=1;i<(1<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>i&1){++len;mat[len][len]=0;for(int j=0,t=0;j>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<>j&1) continue;if(adj[i]>>j&1) inc(path[s|(1<>i&1) f[sz][s]=(ll)__builtin_popcount(adj[i]&s)*f[sz][s]%P;for(int i=lb+1;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<>=1;for(int i=0;i>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)\)，不知是否可行，也不知能否通过。

标签：