自动搬运

查看原文

来自洛谷，原作者为

	BreakPlus empty should not be filled

搬运于2025-08-24 22:59:27，当前版本为作者最后更新于2024-06-17 21:44:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于“异或图”必须同时考虑所有点和边，对点进行状压显得毫无意义。发现 $n \le 10$ 提示我们可能有奇怪复杂度做法。比如，$\text{Bell}(n)$？

正难则反，考虑将图强行拆成不连通图。

钦定将图分为 $x$ 个连通块，两两之间没有连边。但是我们并没有保证连通块内部是否真的联通。

令 $G(x)$ 表示钦定了 $x$ 个连通块的方案数，$F(x)$ 表示恰好有 $x$ 个连通块的方案数。注意到以下两点：

• $G(x)$ 可以在 $\mathcal{O}(\operatorname{poly}(n)\operatorname{Bell}(n))$ 的复杂度求得。

具体地，枚举所有拆分方案，然后钦定连通块之间必须边权位 $0$，令 $x_i$ 表示第 $i$ 个图选还是不选，能列出一堆关于 $x_i$ 的异或方程。

这个异或方程必然有解，根据经典线代结论，解的个数是 $s - t$，其中 $t$ 是线性基的大小（矩阵的秩）。于是就能算了。

• $G(x)$ 可以与 $F(x)$ 建立关系。

不难得到 $G(x) = \sum \limits_{k=x}^n S(k,x)F(k)$，其中 $S$ 是第二类 Stirling 数。

$n$ 很小其实都可以爆解方程。但是这里有一个斯特林反演的结论，上式等价于：

$F(x) = \sum \limits_{k=x}^n (-1)^{k-x}s(k,x)G(k)$

其中 $s$ 是第一类 Stirling 数。

算出 $G$ 后求得 $F(1)$ 即可。

于是就做完了。

哎，一车典题不会，还是似一似吧。

ll n,s; char str[205];
bool E[65][15][15];
struct Basis{
    ll p[65], cnt;
    void clear(){ memset(p,0,sizeof(p)); cnt=0;}
    void insert(ll x){
        for(ll i=60;i>=0;i--){
            if((x>>i)&1){
                if(!p[i]){
                    p[i] = x;
                    ++cnt; break;
                }else x ^= p[i];
            }
        }
    }
}B;
ll c[65], f[65], ans, pw[65];
void dfs(ll x,ll col){
    if(x == n+1){
        B.clear();
        for(ll p=1;p<=n;p++){
            for(ll q=p+1;q<=n;q++){
                if(c[p] == c[q]) continue;
                ll trv = 0;
                for(ll i=1;i<=s;i++)
                    if(E[i][p][q]) trv |= (1ll<<i-1);
                B.insert(trv);
            }
        }
        ans = (ans + f[col] * pw[s - B.cnt]);
        return;
    }
    for(ll i=1;i<=col+1;i++) {
        c[x] = i;
        dfs(x+1, max(i, col));
    }
}
void solve(){
    pw[0] = 1;
    for(ll i=1;i<=60;i++) pw[i] = pw[i-1] * 2;
    s=read();
    for(ll i=1;i<=s;i++){
        scanf("%s", str); ll now=0;
        if(i==1){
            for(ll j=2;j<=10;j++){
                if(j*(j-1)/2==strlen(str)){
                    n=j;
                    break;
                }
            }
        }
        for(ll p=1;p<=n;p++){
            for(ll q=p+1;q<=n;q++){
                E[i][p][q] = E[i][q][p] = str[now++]-'0';
            }
        }
    }
    
    for(ll i=1;i<=n;i++){
        if(i&1) f[i] = Fac(i-1);
        else f[i] = -Fac(i-1);
    }
    dfs(1, 0);
    printf("%lld\n", ans);
}