BZOJ 4671: 异或图

### Description
定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与
G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中.
现在给定 s 个结点数相同的图 G1...s, 设 S = {G1, G2, . . . , Gs}, 请问 S 有多少个子集的异
或为一个连通图?
### Input
第一行为一个整数s, 表图的个数.
接下来每一个二进制串, 第 i 行的二进制串为 gi, 其中 gi 是原图通过以下伪代码转化得
到的. 图的结点从 1 开始编号, 下面设结点数为 n.
Algorithm 1 Print a graph G = (V, E)
for i = 1 to n do
for j = i + 1 to n do
if G contains edge (i, j) then
print 1
else
print 0
end if
end for
end for
 2 ≤ n ≤ 10,1 ≤ s ≤ 60.
### Output
输出一行一个整数, 表示方案数
### Sample Input
```
3 
1 
1 
0
```
### Sample Output
```
4
```

一道好题。
我们发现直接算连通的不太好算。

考虑恰好有$k$个连通块的方案为$f(k)$
至少有$k$个连通块的方案为$g(k)$
通过观察可以发现，一个$f(k)$在$g(n)$中被算了$\left\{ \begin{matrix}n\\ k\end{matrix} \right\}$次，为什么呢？

考虑把$n$个连通块再看成点，划分到$k$个子集方案数就是$\left\{ \begin{matrix}n\\ k\end{matrix} \right\}$。
于是就有了：

$$g(n)=\sum^{n}_{i=1}\left\{ \begin{matrix}n\\ i\end{matrix} \right\} f(i)$$

我们知道，$g(k)$是好算的。发现$n\le 10$，直接枚举每一种划分，强制让划分之间的边为$0$，对每一位列方程直接高斯消元即可，而且不会无解。
高斯消元压压位，复杂度就是$O(\sum^{n}_{i=0}\left\{ \begin{matrix}n\\ k\end{matrix} \right\}\frac{n^3}{bit})=O(B_n\frac{n^3}{bit})$

其中$B_n$是贝尔数。

剩下的问题就是知道$g$如何求$f$了。

考虑斯特林数的一个性质：

$$\sum_{k}\left\{ \begin{matrix}n\\ k\end{matrix} \right\}\left[ \begin{matrix}k\\ m\end{matrix} \right](-1)^{n-k}=[m=n]$$

于是可以反演
$$f(n)=\sum^{n}_{i=1}\left[ \begin{matrix}n\\ i\end{matrix} \right](-1)^{n-i}g(i)$$
就可以做了

```
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define Sub(i, x) for(register int i = x; i; i = x & (i - 1))
#define lowbit(x) ((x) & (-(x)))
#define LL long long
using namespace std;
LL a[64], x, U, V, f[64], g[64], msk[64][64]; int n, N, M;
char s[64];
namespace Gauss {
    LL mat[64]; int d;
    void init(LL mask) {
        memset(mat, 0, sizeof(mat)), d = 0;
        int i; LL pi;
        for(i = 0, pi = 1; pi <= mask; ++i, pi <<= 1) {
            if(!(mask & pi)) continue;
            int j; LL pj;
            for(j = 1, pj = 1; j <= n; ++j, pj <<= 1)
                if(a[j] & pi) mat[d] |= pj;
            d++;
        }
    }
    LL work() {
        int now = 0, p = -1;
        int i; LL pi;
        for(i = 0, pi = 1; i < n; ++i, pi <<= 1) {
            p = -1;
            for(register int j = now; j < d; ++j)
                if(mat[j] & pi) {p = j; break;}
            if(p == -1) continue;
            swap(mat[p], mat[now]);
            for(register int j = 0; j < d; ++j) {
                if(j == now) continue;
                if(pi & mat[j]) 
                    mat[j] ^= mat[now];
            }
            ++now;
        }
        return 1ll << n - now;
    }
}
int lt[64], lcnt;
int stk[64], top, bell;
void dfs(int mask, int mn) {
    if(mask == U) {
        LL lim = 0;
        for(register int i = 1; i <= lcnt; ++i) {
            top = 0;
            for(register int j = 1, pj = 1; j <= N; ++j, pj <<= 1)
                if(pj & (lt[i])) stk[++top] = j;
            for(register int j = 1; j <= top; ++j)
                for(register int k = j + 1; k <= top; ++k)
                    lim |= msk[stk[j]][stk[k]];
        }
        lim = (V - lim);
        Gauss::init(lim);
        f[lcnt] += Gauss::work();
        //++bell;
        return ;
    }
    Sub(i, U - mask - mn) {
        lt[++lcnt] = i | mn;
        dfs(mask | i | mn, lowbit((~(mask | i | mn))));
        --lcnt;
    }
    lt[++lcnt] = mn;
    dfs(mask | mn, lowbit((~(mask | mn))));
    --lcnt;
}
 
LL S1[105][105];
 
void pre(int n) {
    S1[0][0] = 1;
    for(register int i = 1; i <= n; ++i)
        for(register int j = 0; j <= i; ++j) {
            S1[i][j] = (i - 1) * S1[i - 1][j] + S1[i - 1][j - 1];
        }
}
 
int pow_1(int x) {
    return x & 1 ? -1 : 1;
}
 
int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i) {
        scanf("%s", s);
        for(register int j = strlen(s) - 1; j >= 0; --j)
            if(s[j] == '1') a[i] |= (1ll << j);
    }
    M = strlen(s);
    N = (1 + (int)sqrt(8 * M + 1)) / 2;
    U = (1ll << N) - 1;
    V = (1ll << M) - 1;
    int ecnt = 0;
    for(register int i = 1; i <= N; ++i) {
        for(register int j = i + 1; j <= N; ++j)
            msk[i][j] = 1ll << ecnt, ++ecnt;
    }
    pre(12), dfs(0, 1);
    for(register int i = 1; i <= N; ++i) {
        for(register int j = 1; j <= N; ++j)
            g[i] += S1[j][i] * pow_1(j - i) * f[j];
    }
    //printf("%d\n", bell);
    printf("%lld", g[1]);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链