BZOJ 4671 异或图

发表于 | 分类于

Description

定义两个点数相同的图\(G_1,G_2\)的异或为一个新图\(G\)。\(G\)的点数和原来两个图一样，并且对于一条边\((i, j)\)，如果在\(G_1,G_2\)中的出现次数异或起来为\(1\)的话，那么\((i, j)\)会出现在\(G\)中，反之则不会出现。

给出\(s\)个有\(n\)个点的图\(G_1, G_2,\ldots,G_s\)，求这些图有多少个子集异或起来得到的图是一个联通图。

\(2\leq n\leq 10, 1\leq s\leq 60\)。

Solution

数数题，启动！

恰好有一个连通块的情况是不好统计的，但是至少有一个连通块的情况很好统计。我们只需要枚举\(n\)个点的集合划分（\(B_{10} = 21147\)，所以不虚），保证不同集合之间没有边就行了。这样假设划出来了\(c\)个集合，那么最后的连通块数一定不小于\(c\)。

考虑不同集合之间没有边的条件如何处理。注意到这样就要求了包含这条边的图只用了偶数个，那么把所有这种条件列成一个方程组就是一个\(s\)元异或方程组。而我们知道一个\(s\)元异或方程组（假设其矩阵为\(A\)）的解数为\(2^{s - r(A)}\)，而\(r(A)\)就等于该矩阵的线性基数量，用线性基那一套传统艺能就可以求了。

然后我们现在只求出了至少\(c\)个连通块的方案，要想知道只有一个连通块的方案，势必要容斥一下。根据容斥系数那一套理论，我们要求右边的条件是\([n = 1]\)，因此容斥系数\(\mathrm{coef}_i\)应当满足： \[ \sum_{i = 1}^n \begin{Bmatrix}n\\i\end{Bmatrix}\mathrm{coef}_i = [n = 1] \] 使用打表等传统艺能可知\(\mathrm{coef}_i = (-1)^{i - 1}(i - 1)!\)，然后这题就做完力……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
typedef long long ll;
const int maxn = 12;
const int maxs = 62;
const int maxm = 60;
ll lowbit(ll x) {
  return x & (-x);
}

int n, m, s;
ll L[maxn][maxn];
ll M[maxm];
ll gj() {
  static ll bas[maxs];
  std::fill(bas, bas + s, 0LL);
  int cnt = 0;
  for(int i = 1; i <= m; i ++) {
    ll x = M[i];
    for(int j = s - 1; j >= 0; j --) {
      if(!((1LL << (ll(j))) & x)) continue;
      if(bas[j]) {
        x ^= bas[j];
      } else {
        cnt ++; bas[j] = x;
        break;
      }
    }
  }
  return (1LL << (ll(s - cnt)));
}

int bel[maxn]; ll f[maxn];
void dfs(int x, int cnt) {
  if(x > n) {
    m = 0;
    for(int i = 1; i <= n; i ++) {
      for(int j = i + 1; j <= n; j ++) {
        if(bel[i] == bel[j]) continue;
        M[++ m] = L[i][j];
      }
    }
    f[cnt] += gj();
    return;
  }
  for(int i = 1; i <= cnt + 1; i ++) {
    bel[x] = i;
    dfs(x + 1, std::max(i, cnt));
  }
}

int main() {
  scanf("%d", &s);
  for(int i = 0; i < s; i ++) {
    char S[maxs]; scanf("%s", S);
    if(!n) {
      int l = strlen(S);
      n = (1 + (int((sqrt(1 + 8 * l))))) / 2;
    }
    int cnt = 0;
    for(int j = 1; j <= n; j ++) {
      for(int k = j + 1; k <= n; k ++) {
        if(S[cnt] == '1') {
          L[j][k] ^= (1LL << (ll(i)));
        }
        cnt ++;
      }
    }
  }
#ifdef LOCAL
  printf("n : %d\n", n);
#endif
  dfs(1, 0);
  ll ans = 0, fac = 1;
  for(int i = 1; i <= n; i ++) {
    ll delta = fac * f[i];
    if(!(i & 1)) delta *= -1LL;
#ifdef LOCAL
    printf("delta(%d) : %lld\n", i, delta);
#endif
    ans += delta;
    fac *= (ll)i;
  }
  printf("%lld\n", ans);
  return 0;
}