P10591 BZOJ4671 异或图

Genius_Star · 2026-08-29 09:49:03 · 题解

或许更好的阅读体验。

思路：

考虑容斥一波，定义 f_i 表示最终恰好有 i 个连通块的方案数，再定义钦定图中有 i 个连通块的方案数（即块内任意连，可以不是一个连通块，但是块间没有边），那么显然有：

斯特林反演后有：

我们要算 f_1，那么只需要算 g 即可。

注意到 n \le 10，考虑枚举连通块的划分，是 \operatorname{Bell}(n) 级别，比较小；现在问题相当于钦定了一些连通块，然后需要选一些图把不需要的边异或掉，问解的个数。

令 E 为我们不需要的边，对于每个图 G_i 算出 G_i \cap E 后，看作若干个二进制数，于是相当于选择若干个数异或起来是全 0 的方案数；显然可以建线性基，那么设线性基大小是 siz，那么方案数显然是 2^{s - siz}，即其它可以任意选，然后用基底去调整成 0。

最后答案是：

时间复杂度为 O(\operatorname{Bell}(n) s n^2)，可以通过。

完整代码：

 #include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define ctz(x) __builtin_ctz(x)
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 61, M = 45;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
ll ans;
int n, s;
char str[N];
ll a[N], g[N], fac[N];
class Xor{
public:
    int siz;
    ll a[M];
    inline void init(){
        siz = 0;
        memset(a, 0, sizeof(a));
    }
    inline void ins(ll x){
        for(int i = M - 1; i >= 0; --i){
            if((x >> i) & 1){
                if(!a[i]){
                    a[i] = x;
                    ++siz;
                    break;
                }
                else
                  x ^= a[i];
            }
        }
    }
}T;
int col[N];
inline ll calc(ll S){
    T.init();
    for(int i = 1; i <= s; ++i)
      T.ins(S & a[i]);
    // cerr << T.siz << '\n';
    return 1ll << (s - T.siz);
}
inline void dfs(int pos, int num){
    if(pos == n + 1){
        ll S = 0;
        int now = 0;
        for(int i = 1; i <= n; ++i){
            for(int j = i + 1; j <= n; ++j){
                if(col[i] != col[j])
                  S |= (1ll << now);
                ++now;
            }
        }
        // cerr << S << '\n';
        // cerr << num << ' ' << calc(S) << '\n';
        g[num] += calc(S);
        return ;
    }
    for(int i = 1; i <= num + 1; ++i){
        col[pos] = i;
        dfs(pos + 1, max(num, i));
    }
}
int main(){
    s = read();
    for(int i = 1; i <= s; ++i){
        scanf("%s", str);
        int m = strlen(str);
        if(!n){
            n = 1;
            for(int i = 2; i <= 10; ++i){
                if(i * (i - 1) == m * 2){
                    n = i;
                    break;
                }
            }
        }
        for(int j = 0; j < m; ++j)
          if(str[j] == '1')
            a[i] |= (1ll << j);
    }
    dfs(1, 0);
    fac[0] = 1;
    for(int i = 1; i <= n; ++i){
        // cerr << g[i] << '\n';
        fac[i] = 1ll * i * fac[i - 1];
        if((i - 1) & 1)
          ans -= fac[i - 1] * g[i];
        else
          ans += fac[i - 1] * g[i];
    }
    write(ans);
    return 0;
}