点这里看题目。
手玩容易发现 good graph 的第二条要求等价于 \(G'\) 是二分图。
说明:
设 \(x_u\) 表示某种方案中 \(u\) 是否被操作。
那么有 \(|E'|\) 条方程。对于 \((u,v)\in E'\),方程的形式为 \(x_u\oplus x_v=1\)。
取出任意的相邻两条边,比如 \((u,v),(v,w)\),将两条方程异或起来得到 \(x_u=x_w\)。
那么 \(x\) 对应了一种黑白染色方案,而当且仅当 \(G'\) 是二分图的时候,才会存在合法的 \(x\)。
考虑二分图比较好用的性质:有且仅有二分图可以被黑白染色。那么限制变成:
注意到“可以被黑白染色”这条限制明显比“连通”难处理得多,因此我们优先处理掉第二条限制。
设 \(G[S]\) 为点集 \(S\) 在 \(G\) 上的导出子图,\(G[S]=(S,E[S])\)。我们可以设 \(f_S\) 为所有 \(G'=(S,E'),E'\subseteq E[S]\) 的黑白染色方案的数量之和。这个很容易计算,我们只需要枚举哪些染白、哪些染黑,则边一定从跨黑白的边之中选出。
\(f\) 中的图有些是不连通的,我们需要再将它们处理掉。这很容易,我们只需要设 \(g_S\) 为所有连通的 \(G'\) 的黑白染色方案的数量之和即可,而 \(g\) 也可以使用 DP 简单地计算。我们可以钦定元素 \(k\in S\),则有:
\[g_S=f_S-\sum_{k\in T\subsetneq S}g_T\times f_{S\setminus T} \]注意到,连通的二分图只有两种黑白染色方案,那么答案即为 \(\frac{1}{2}g_{U}\)。
小结:
#include <cstdio> #define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ ) #define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- ) const int mod = 998244353; const int MAXN = 20, MAXM = 17 * 16 + 5, MAXS = ( 1 << 17 ) + 5; int grp[MAXS]; int f[MAXS], g[MAXS]; int pw[MAXM]; int N, M; inline int Mul( int x, int v ) { return 1ll * x * v % mod; } inline int Sub( int x, int v ) { return ( x -= v ) < 0 ? x + mod : x; } inline int Add( int x, int v ) { return ( x += v ) >= mod ? x - mod : x; } int main() { scanf( "%d %d", &N, &M ); rep( i, 1, M ) { int a, b; scanf( "%d %d", &a, &b ), a --, b --; for( int S = 0 ; S < ( 1 << N ) ; S ++ ) if( ( S >> a & 1 ) && ( S >> b & 1 ) ) grp[S] ++; } pw[0] = 1; rep( i, 1, M ) pw[i] = Mul( pw[i - 1], 2 ); for( int S = 0 ; S < ( 1 << N ) ; S ++ ) { g[S] = 1; for( int T = S ; T ; T = ( T - 1 ) & S ) g[S] = Add( g[S], pw[grp[S] - grp[T] - grp[S ^ T]] ); } f[0] = 1; for( int S = 1 ; S < ( 1 << N ) ; S ++ ) { int low = S & ( - S ); f[S] = g[S]; for( int T = ( S - 1 ) & S ; T ; T = ( T - 1 ) & S ) { if( ! ( T & low ) ) continue; f[S] = Sub( f[S], Mul( f[T], g[S ^ T] ) ); } } printf( "%d\n", Mul( f[( 1 << N ) - 1], ( mod + 1 ) >> 1 ) ); return 0; }