容易发 \(i\) 条边的森林，有 \(n-i\) 棵树，那么有：
令 \(g_k(S)\) 表示点集 \(S\) 形成含有 \(k\) 棵树的森林的方案数
答案为: \(\displaystyle \frac{g_{n-i}(U)i!}{m^i}\)
可以枚举 \(S\) 中任意点所在的树转移，那么记 \(f(S)\) 表示点集 \(S\) 连成树的方案数，有：
\[g_i(S)=\sum_{T \subseteq S}f(T)g_{i-1}(S-T) \]那么可以 \(\mathcal O(n3^n)\) 计算所有 \(g_i(S)\) ，当然可以使用子集卷积做到 \(\mathcal O(n^32^n)\)
现在问题转化为求 \(f(S)\)，当然可以用矩阵树定理 \(\mathcal O(n^3 2^n)\) 解决。
但不妨直接计数，
\[f(S)=\frac{1}{2(|S|-1)}\sum_{T \subset S}f(T)f(S-T)E(T,S-T) \]其中 \(E(S,T)\) 表示 \(S,T\) 之间的边数，令 \(E(S)\) 表示 \(S\) 内部的边数 ，有：
\[E(S,T)=E(S|T)-E(S)-E(T) \]这部分可以 \(\mathcal O(3^n+n^22^n)\) 解决。
那么整个问题可以在 \(\mathcal O(2^nn^3+3^n)\) 内解决。
总结
大部分图计数都可以通过划分联通快形成子问题，从而求解。
#include <bits/stdc++.h>
using namespace std;
#define pc __builtin_popcount
const int MAXN = 14 , MAXM = 500 , Mod = 998244353;
inline int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
inline int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
inline int Mul( int x , int y ) { return 1ll * x * y % Mod; }
inline int Qkpow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) p = Mul( p , x ); return p; }
inline int Inv( int x ) { return Qkpow( x , Mod - 2 ); }
int fac[ 105 ] , ivf[ 105 ] , iv[ 105 ];
void fwtor( int n , int *f , int op ) {
for( int len = 2 ; len <= n ; len <<= 1 )
for( int l = 0 ; l < n ; l += len )
for( int i = l ; i < l + len / 2 ; i ++ )
f[ i + len / 2 ] = Add( f[ i + len / 2 ] , op == 1 ? f[ i ] : Sub( 0 , f[ i ] ) );
}
int fs[ MAXN + 1 ][ 1 << MAXN ] , gs[ MAXN + 1 ][ 1 << MAXN ] , hs[ MAXN + 1 ][ 1 << MAXN ];
void fst( int n , int *f , int *g , int *h ) {
for( int i = 0 ; i < 1 << n ; i ++ ) fs[ pc( i ) ][ i ] = f[ i ] , gs[ pc( i ) ][ i ] = g[ i ];
for( int i = 0 ; i <= n ; i ++ ) fwtor( 1 << n , fs[ i ] , 1 ) , fwtor( 1 << n , gs[ i ] , 1 );
for( int i = 0 ; i <= n ; i ++ )
for( int j = 0 ; j <= n - i ; j ++ )
for( int k = 0 ; k < 1 << n ; k ++ )
hs[ i + j ][ k ] = Add( hs[ i + j ][ k ] , Mul( fs[ i ][ k ] , gs[ j ][ k ] ) );
for( int i = 0 ; i <= n ; i ++ ) fwtor( 1 << n , hs[ i ] , -1 );
for( int i = 0 ; i < 1 << n ; i ++ ) h[ i ] = hs[ pc( i ) ][ i ];
for( int i = 0 ; i <= n ; i ++ ) for( int j = 0 ; j < 1 << n ; j ++ ) fs[ i ][ j ] = gs[ i ][ j ] = hs[ i ][ j ] = 0;
}
int n , m , G[ MAXN ][ MAXN ] , E[ 1 << MAXN ];
int f[ 1 << MAXN ] , g[ MAXN + 1 ][ 1 << MAXN ];
inline int Ecnt( int S , int T ) { return E[ S | T ] - E[ S ] - E[ T ]; }
int main( ) {
fac[ 0 ] = 1; ivf[ 0 ] = 1;
for( int i = 1 ; i <= 100 ; i ++ ) {
fac[ i ] = Mul( fac[ i - 1 ] , i );
ivf[ i ] = Inv( fac[ i ] ); iv[ i ] = Inv( i );
}
scanf("%d %d",&n,&m);
for( int i = 1 , u , v ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v); u -- , v --;
G[ u ][ v ] ++; G[ v ][ u ] ++;
}
for( int S = 0 ; S < 1 << n ; S ++ ) {
for( int i = 0 ; i < n ; i ++ ) if( ( S >> i ) & 1 )
for( int j = i ; j < n ; j ++ ) if( ( S >> j ) & 1 )
E[ S ] += G[ i ][ j ];
}
for( int S = 1 ; S < 1 << n ; S ++ ) {
if( pc( S ) == 1 ) { f[ S ] = 1; continue; }
for( int T = S ; T ; T = ( T - 1 ) & S )
f[ S ] = Add( f[ S ] , Mul( Mul( f[ T ] , f[ S ^ T ] ) , Ecnt( T , S ^ T ) ) );
f[ S ] = Mul( f[ S ] , iv[ 2 * ( pc( S ) - 1 ) ] );
}
g[ 0 ][ 0 ] = 1;
for( int i = 1 ; i < n ; i ++ ) {
// for( int S = 0 ; S < 1 << n ; S ++ ) {
// for( int T = S ; T ; T = ( T - 1 ) & S )
// g[ i ][ S ] = Add( g[ i ][ S ] , Mul( f[ T ] , g[ i - 1 ][ S ^ T ] ) );
// }
fst( n , f , g[ i - 1 ] , g[ i ] );
for( int S = 0 ; S < 1 << n ; S ++ )
g[ i ][ S ] = Mul( g[ i ][ S ] , iv[ i ] );
}
for( int i = 1 ; i < n ; i ++ )
printf("%d\n", Mul( Mul( g[ n - i ][ ( 1 << n ) - 1 ] , fac[ i ] ) , Inv( Qkpow( m , i ) ) ) );
return 0;
}