[BZOJ4671]异或图

2018/03/02 09:02
阅读数 13

###[BZOJ4671]异或图

####试题描述 定义两个结点数相同的图 $G_1$ 与图 $G_2$ 的异或为一个新的图 $G$, 其中如果 $(u, v)$ 在 $G_1$ 与 $G_2$ 中的出现次数之和为 $1$, 那么边 $(u, v)$ 在 $G$ 中, 否则这条边不在 $G$ 中.

现在给定 $s$ 个结点数相同的图 $G_{1 \sim s}$, 设 $S = {G_1, G_2, \cdots , G_s}$, 请问 $S$ 有多少个子集的异或为一个连通图?

####输入 第一行为一个整数 $s$, 表图的个数.

接下来每一个二进制串, 第 $i$ 行的二进制串为 $g_i$, 其中 $g_i$ 是原图通过以下伪代码转化得到的. 图的结点从 $1$ 开始编号, 下面设结点数为 $n$.

Algorithm 1 Print a graph G = (V, E)
    for i = 1 to n do
        for j = i + 1 to n do
            if G contains edge (i, j) then
                print 1
            else
                print 0
            end if
        end for
    end for

####输出 输出一行一个整数, 表示方案数

####输入示例

3
1
1
0

####输出示例

4

####数据规模及约定 $2 \le n \le 10,1 \le s \le 60$.

####题解 连通性计数相关的问题一般要用到容斥原理,这是因为“连通”非常难处理,因为整体连通并不知道每条边的存在情况,而“不连通”则是可以确定没有任何边相连;而容斥就是用 $连通方案 = 总方案 - 不连通方案$,从而将连通计数问题转化为不连通计数的问题。

此题就是考虑计算“不连通”的情况。我们需要枚举节点的子集划分,不同的子集之间的节点没有任何边相连,同一子集中的点连边情况则没有限制,令我们划分的子集个数为 $m$,且在所有 $m$-划分的情况下计算的方案总和为 $f_m$,并令 $g_m$ 表示恰好有 $m$ 个连通块的方案数,显然 $f_m \ge g_m$,因为我们算的还有内部不连通的情况。

更加具体一点,其实是满足这样一个关系

$$ f_m = \sum_{i=m}^n \begin{Bmatrix} i \ m \end{Bmatrix} g_i $$

其中 $\begin{Bmatrix} i \ m \end{Bmatrix}$ 表示第二类斯特林数“$i$ 子集 $m$”。显然对于每种 $g_i(i \ge m)$,$i$ 个集合之间是没有考虑顺序的,而我们计算出来的 $f_m$ 则会将某个多出来的集合并到那 $m$ 个集合中某个集合里面去,所以它需要乘上一个子集划分。

根据斯特林反演可以得到

$$ g_m = \sum_{i=m}^n (-1)^{i-m} \begin{bmatrix} i \ m \end{bmatrix} f_i $$

现在我们只要求 $g_1$,所以

$$ g_1 = \sum_{i=1}^n (-1)^{i-1} (i-1)! f_i $$

现在主要问题就是 $f_m$ 如何求。我们可以枚举子集划分,然后某些边的状态确定了,这时我们令 $x_1, x_2, \cdots , x_s$ 分别表示图 $G_1, G_2, \cdots , G_s$ 的选择情况($x_i = 1$ 表示选择 $G_i$,$x_i = 0$ 表示不选),那么对于每一条确定的边我们都能得到一个异或方程,那么会得到一个若干个异或方程组成的异或方程组,我们对它进行高斯消元就能知道主元的个数 $c$ 了,那么方案数就是 $2^{s-c}$,把这个方案数累加到 $f_m$($m$ 是当前枚举的子集划分中子集的个数)中。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxs 65
#define maxn 15
#define maxe 50
#define LL long long

char str[maxe];
int s, n, gr[maxs][maxn][maxn];

LL ans, A[maxe], fac[maxn];
int bl[maxn];
void solve(int cur, int m) {
	if(cur >= n) {
		memset(A, 0, sizeof(A));
		rep(i, 0, n - 1) rep(j, i + 1, n - 1) if(bl[i] != bl[j]) {
			LL tmp = 0;
			rep(g, 0, s - 1) tmp |= (LL)gr[g][i][j] << g;
			dwn(k, maxe - 1, 0) if(tmp >> k & 1) {
				if(A[k]) tmp ^= A[k];
				else{ A[k] = tmp; break; }
			}
		}
		int c = 0;
		rep(k, 0, maxe - 1) c += A[k] > 0;
		ans += ((m & 1) ? 1ll : -1ll) * (1ll << s >> c) * fac[m-1];
		return ;
	}
	rep(i, 1, m + 1) bl[cur] = i, solve(cur + 1, max(m, i));
	return ;
}

int main() {
	s = read();
	rep(i, 0, s - 1) {
		scanf("%s", str);
		int l = strlen(str), t = 0;
		n = (1 + sqrt(1 + (l << 3))) / 2;
		rep(x, 0, n - 1) rep(y, x + 1, n - 1) gr[i][x][y] = str[t++] - '0';
	}
	
	fac[0] = 1;
	rep(i, 1, n) fac[i] = fac[i-1] * i;
	solve(0, 0);
	
	printf("%lld\n", ans);
	
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部