Solution P10591 | Striling Inversion

· · 题解

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

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

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

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

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

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

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

$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);
}