Description
定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中. 现在给定 s 个结点数相同的图 G1…s, 设 S = {G1, G2, … , Gs}, 请问 S 有多少个子集的异或为一个连通图?
Solution
考虑枚举每一种点集的划分方式，我们可以用线性基方便地算出点集之间一定没有边的方案数，但是这样不能保证点集内部一定联通，所以就需要容斥一下。 设
m
m
为枚举的点集的个数，则容斥系数fifi满足：
∑i=1m{mi}fi=[m=1]
∑
i
=
1
m
{
m
i
}
f
i
=
[
m
=
1
]
由斯特林反演有：
∑i=1m[i=1](−1)m−i[mi]=fm
∑
i
=
1
m
[
i
=
1
]
(
−
1
)
m
−
i
[
m
i
]
=
f
m
即：
fm=(−1)m−1(m−1)!
f
m
=
(
−
1
)
m
−
1
(
m
−
1
)
!
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<
int,
int> PII;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia
template <
typename T>
inline bool chkmax(T &a, T b) {
return a < b ? a = b,
1 :
0; }
template <
typename T>
inline bool chkmin(T &a, T b) {
return b < a ? a = b,
1 :
0; }
inline int read()
{
register int _, __;
register char c_;
for (_ =
0, __ =
1, c_ = getchar(); c_ <
'0' || c_ >
'9'; c_ = getchar())
if (c_ ==
'-') __ = -
1;
for ( ; c_ >=
'0' && c_ <=
'9'; c_ = getchar()) _ = (_ <<
1) + (_ <<
3) + (c_ ^
48);
return _ * __;
}
const int maxs =
61, maxn =
11;
struct Edge
{
int u, v;
Edge(
int u =
0,
int v =
0): u(u), v(v) {}
}E[maxn * maxn >>
1];
int s, len, n, G[maxs][maxn][maxn], id[maxn];
LL f[maxn], base[maxn * maxn], Ans;
char str[maxs][maxn * maxn];
void DFS(
int cur,
int cnt)
{
if (cur > n) {
Set(base,
0);
int tot =
0, sum =
0;
For(i,
1, n) For(j, i +
1, n)
if (id[i] != id[j]) E[++ tot] = Edge(i, j);
For(i,
1, s) {
LL val =
0;
For(j,
1, tot)
if (G[i][E[j].u][E[j].v]) val |= (
1ll << j);
Fordown(j, tot,
1)
if (val >> j &
1ll)
if (!base[j]) { base[j] = val, ++ sum;
break; }
else val ^= base[j];
}
Ans += f[cnt] * (
1ll << (s - sum));
}
else For(i,
1, cnt +
1) id[cur] = i, DFS(cur +
1, max(cnt, i));
}
int main()
{
#ifdef hany01
File(
"bzoj4671");
#endif
s = read();
For(i,
1, s)
scanf(
"%s", str[i]);
len =
strlen(str[
1]);
n =
int(
sqrt(len <<
1)) +
1;
For(k,
1, s) {
int cnt =
0;
For(i,
1, n) For(j, i +
1, n) G[k][i][j] = str[k][cnt ++] ^
48;
}
f[
1] =
1;
For(i,
2, n) f[i] = f[i -
1] * (LL)(
1 - i);
DFS(
1,
0);
printf(
"%lld\n", Ans);
return 0;
}
