BZOJ4671：异或图

传送门
直接求连通的不好做，考虑容斥
设 \(g_i\) 表示至少有 \(i\) 个连通块的方案数，\(f_i\) 表示恰好有 \(i\) 个的
那么
\[g_x=\sum_{i=x}^{n}\begin{Bmatrix}x \\ i\end{Bmatrix}f_i\iff f_x=\sum_{i=x}^{n}(-1)^{i-x}\begin{bmatrix}x \\ i\end{bmatrix}g_i\]
那么
\[f_1=\sum_{i=1}^{n}(-1)^{i-1}(i-1)!g_i\]
求 \(g\)
考虑枚举点的拆分，相当于是不同的集合之没有边，这部分直接用线性基求出方案

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n = 1, graph[65][15][15], m, id[15];
char ch[2333];
ll fac[15], ans, bc[65], v;

void Dfs(int x, int f) {
    register int i, j, k, tot, num;
    if (x > n) {
        memset(bc, 0, sizeof(bc)), num = 0;
        for (i = 1; i <= m; ++i) {
            for (v = tot = 0, j = 1; j <= n; ++j)
                for (k = j + 1; k <= n; ++k)
                    if (id[j] != id[k]) v |= (ll)graph[i][j][k] << tot, ++tot;
            for (j = 0; j < tot; ++j)
                if (v >> j & 1) {
                    if (!bc[j]) {
                        bc[j] = v, ++num;
                        break;
                    }
                    v ^= bc[j];
                }
        }
        ans += (ll)((f & 1) ? 1 : -1) * fac[f - 1] * (1ll << (m - num));
        return;
    }
    for (i = 1; i <= f + 1; ++i) id[x] = i, Dfs(x + 1, max(i, f));
}

int main() {
    register int i, j, k, len, cnt;
    for (scanf("%d", &m), i = 1; i <= m; ++i) {
        scanf(" %s", ch + 1), len = strlen(ch + 1);
        while (n * (n - 1) / 2 < len) ++n;
        for (cnt = 0, j = 1; j <= n; ++j)
            for (k = j + 1; k <= n; ++k) graph[i][j][k] = ch[++cnt] - '0';
    }
    for (fac[0] = 1, i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i;
    Dfs(1, 0), printf("%lld\n", ans);
    return 0;
}

BZOJ4671：异或图

原文：https://www.cnblogs.com/cjoieryl/p/10182369.html