【bzoj4671】异或图（容斥+斯特林反演+线性基）

传送门

题意：

给出\(s,s\leq 60\)张图，每张图都有\(n,n\leq 10\)个点。

现在问有多少个图的子集，满足这些图的边“异或”起来后，这张图为连通图。

思路：

直接考虑判断图的连通不好判断，所以考虑枚举连通块来进行容斥。

定义\(f_i\)表示有\(i\)个连通块的答案，发现连通块这个东西也不好处理，我们只能处理出有多少个连通块，但无法确定每个连通块内部的连通关系。

定义\(g_i\)为至少有\(i\)个连通块的方案数，那么就有关系式：\(\displaystyle g_i=\sum_{j=i}^n \begin{Bmatrix}
j \\ i
\end{Bmatrix}f_j\)。至于为什么要乘以一个第二类斯特林数，相当于我们将单个的连通块再进行组合，有不同的组合方式。

此时\(g_i\)就相当于有\(i\)个连通块，内部可连通可不连通的方案数。

因为最终所求为\(f_1\)，通过斯特林反演可得：\(\displaystyle f_1=\sum_{i=1}^n(-1)^{i-1}\begin{bmatrix}
i \\ 1
\end{bmatrix}g_i\)。那么现在只需要算\(g_i\)即可。

因为点数很少，可以直接枚举子集划分，我们只需要保证最后不同的集合之间没有边相连即可。

当确定了一种子集划分过后，将连接不同集合的边拿出来，将每张图这类边转为二进制插入线性基中，最后的基为\(c\)个，那么答案就为\(2^{s-c}\)。

将答案累加入\(f_i\)即可。

这个题大概就这样做完了，但还有一些小细节，其中，斯特林反演的时候和常见形式稍有不同，但可以通过反转公式证明：

\[\left\{
\begin{aligned}
&\sum_{k=m}^n(-1)^{n-k}\begin{bmatrix}
n \\ k
\end{bmatrix}\begin{Bmatrix}
k \\ m
\end{Bmatrix}=[n=m]\\
&\sum_{k=m}^n(-1)^{k-m}\begin{Bmatrix}
n \\ k
\end{Bmatrix}\begin{bmatrix}
k \\ m
\end{bmatrix}=[n=m]
\end{aligned}
\right.
\]

最后的答案为\(2^{s-c}\)的原因在于，我们相当于来求若干个数异或起来为\(0\)的方案数，每个图用\(x_i\)来表示其最终状态，那么如果有\(c\)个基，说明就有\(s-c\)个自由变量，对于任意一组自由变量的取值，我们都能找到一组唯一的对应的解满足方程。

其实这个本质上就是求解一个异或方程组。

代码如下：

/*

 * Author:  heyuhhh

 * Created Time:  2019/12/17 15:36:21

 */

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <iomanip>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

#define INF 0x3f3f3f3f

#define Local

#ifdef Local

  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

  void err() { std::cout << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 105;

int s, n;

char ch[N];

int G[N][N][N];

int a[N];

ll p[64], fac[N];

ll ans;

void dfs(int x, int up) {

    if(x == n) {

        memset(p, 0, sizeof(p));

        int c = 0;

        for(int k = 1; k <= s; k++) {

            ll res = 0;

            int tot = 0;

            for(int i = 1; i <= n; i++) {

                for(int j = i + 1; j <= n; j++) {

                    if(a[i] != a[j]) res |= ((ll)G[k][i][j] << tot);

                    ++tot;

                }

            }

            for(int i = tot; i >= 0; i--) if(res >> i & 1) {

                if(!p[i]) {

                    ++c; p[i] = res;

                    break;

                }

                res ^= p[i];

            }

        }

        if(up & 1) ans += fac[up - 1] * (1ll << (s - c));

        else ans -= fac[up - 1] * (1ll << (s - c));

        return;

    }

    for(int i = 1; i <= up + 1; i++) {

        a[x + 1] = i; dfs(x + 1, max(i, up));

    }

}

void run(){

    fac[0] = 1;

    for(int i = 1; i < 12; i++) fac[i] = fac[i - 1] * i;

    for(int k = 1; k <= s; k++) {

        cin >> (ch + 1);

        int len = strlen(ch + 1), cnt = 0;

        for(int j = 1; !n; j++) if(j * (j - 1) == 2 * len) n = j;

        for(int i = 1; i <= n; i++) {

            for(int j = i + 1; j <= n; j++) {

                G[k][i][j] = ch[++cnt] - '0';

            }

        }

    }

    a[1] = 1;

    dfs(1, 1);

    cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    while(cin >> s) run();

    return 0;

}