题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=4671
题解
半年前刚学计数的时候对这道题怀着深深的景仰，现在终于可以来做这道题了。
类似于一般的容斥和反演题，我们发现整个图是联通的图非常不好求。于是我们转化为整个图钦定了有 (i) 个块必须不连通，其余任意的方案数。
然后考虑这个怎么求，我们可以暴力枚举一下把这些数分成很多组，显然方案数就时 (B_n)（贝尔数，就是 (sumlimits_{i=0}^n egin{Bmatrix}n\iend{Bmatrix}) 的和，在 (n leq 10) 的时候都不超过十万级别）。
然后就是相当于有一些边不能存在，其余的别可以任意存在。考虑用一个线性基来维护。由于边数不超过 (frac{n(n-1)}2)，所以可以用 ll 表示。然后问题转化为一个数有多少个子集存在于线性基中。
但是一个数有多少个子集存在于线性基中不太好维护，经过某位同学的提示，可以想到把那些可以任意为 (0/1) 的位扔掉，只记录只能为 (0) 的位，把这些位扔进线性基。最后只需要用线性基求出有多少种方案使得异或和为 (0) 就可以了。
以下是代码，时间复杂度为 (O(B_nn^2m))。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b , 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b , 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I>
inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
template<typename I>
inline void read2(char *s, I &x) {
int f = 0, c;
while (!isdigit(c = *s++)) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = *s++)) x = (x << 1) + (c & 15);
f ? x = -x : 0;
}
const int N = 45 + 7;
const int M = 60 + 7;
int n, m, sn, ssn;
int a[N], bl[N], ss[N];
ll b[M], f[N], S[N][N];
pii dy[N];
char s[N], p[N];
struct XXJ {
ll a[N];
inline void cls() { memset(a, 0, sizeof(a)); }
inline bool ins(ll x) {
for (int i = ssn - 1; ~i; --i)
if ((x >> i) & 1) {
if (a[i]) x ^= a[i];
else return a[i] = x, 1;
}
return 0;
}
inline int count() {
int cnt = 0;
for (int i = ssn - 1; ~i; --i) if (a[i]) ++cnt;
return cnt;
}
} gg;
inline void calc(int y) {
ss[0] = 0;
for (int i = 0; i < sn; ++i)
if (bl[dy[i].fi] != bl[dy[i].se]) ss[++ss[0]] = i;
ssn = ss[0], gg.cls();
for (int i = 1; i <= m; ++i) {
ll c = 0;
for (int j = ss[0]; j; --j) c = c << 1 | ((b[i] >> ss[j]) & 1);
gg.ins(c);
}
f[y] += 1ll << (m - gg.count());
}
inline void dfs(int x, int y) {
if (x == n + 1) return calc(y);
for (int i = 1; i <= y + 1; ++i) bl[x] = i, dfs(x + 1, std::max(y, i));
}
inline void work() {
dfs(1, 0);
ll ans = 0;
S[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j) S[i][j] = S[i - 1][j - 1] + (i - 1) * S[i - 1][j];
for (int i = 1; i <= n; ++i)
if ((i - 1) & 1) ans -= S[i][1] * f[i];
else ans += S[i][1] * f[i];
printf("%lld
", ans);
}
inline void init() {
read(m);
for (int i = 1; i <= m; ++i) {
scanf("%s", s + 1);
int nn = strlen(s + 1);
std::reverse(s + 1, s + nn + 1);
n = (1 + (int)sqrt(1 + 8 * nn)) >> 1;
read2(s + 1, b[i]);
}
sn = 0;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j) dy[sn++] = pii(i, j);
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}