「ARC105F」Lights Out on Connected Graph

题目

点这里看题目。

分析

手玩容易发现 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'\) 连通;
  • \(G'\) 可以被黑白染色;

注意到“可以被黑白染色”这条限制明显比“连通”难处理得多,因此我们优先处理掉第二条限制

设 \(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}\)。

小结:

  1. 限制较多的时候,一定要注意哪些限制比较难以处理,难以处理的限制一般会通过枚举优先保证的方式来解决;
  2. 本题中,我们没有选择直接对图计数,而是对图染色方案数计数,最终利用性质可以简单地推出答案。很多时候不一定可以方便地直接算出答案,我们最好是计算某些易于计算的量再较快地推出答案

代码

#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;
}
上一篇:Linux下增加swap分区


下一篇:R语言中igraph绘制网络图