[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)，因为我们算的还有内部不连通的情况。
更加具体一点，其实是满足这样一个关系
其中 (egin{Bmatrix} i \ m end{Bmatrix}) 表示第二类斯特林数“(i) 子集 (m)”。显然对于每种 (g_i(i ge m))，(i) 个集合之间是没有考虑顺序的，而我们计算出来的 (f_m) 则会将某个多出来的集合并到那 (m) 个集合中某个集合里面去，所以它需要乘上一个子集划分。
根据斯特林反演可以得到
现在我们只要求 (g_1)，所以
现在主要问题就是 (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
", ans);
return 0;
}