题目大意

给定一个 $n \times n$ 的 $0/1$ 矩阵，其中 $1$ 的位置表示存在一颗恒星。对于任意一个非空子集 $T$（即选中一部分原恒星），定义其价值为：可以无限次在空位上添加新恒星，每次添加必须满足该位置能与至少 $3$ 颗已有恒星直接相连（同行或同列且之间无其他恒星），最终得到的连通分量（星系）的最小个数。要求计算所有非空子集的价值之和，对 $10^9+7$ 取模。

数据范围：$1\le n\le 14$，所有测试用例的 $2^n$ 之和不超过 $2^{14}$。

算法分析

1. 问题转化

对于固定子集 $T$，反复添加所有满足“度 $\ge 3$”的空位，直到不能添加为止，得到的点集称为 $T$ 的闭包 $\overline{T}$。可以证明，最终的最小星系数等于 $\overline{T}$ 中恒星按直接相连定义形成的连通分量数。因此，价值就是闭包图的连通分量数。

由于 $n\le 14$，我们可以用状态压缩表示列集合。整个问题可以通过矩形划分的 DP 来求解所有子集的价值之和。

2. 预处理

设 $cnt(l,r,x,y)$ 表示矩形 $[l,r)\times[x,y)$ 内原矩阵中 $1$ 的个数。令 $v(k)=2^k-1$（非空子集个数），并预处理二维前缀和以便 $O(1)$ 计算矩形内 $1$ 的个数。

对于任意行区间 $[l,r)$ 和列区间 $[x,y)$，定义：

$$g(l,r,x,y)=\sum_{mask=0}^{3}(-1)^{\text{popcount}(mask)}\;v\big(cnt(l+\delta_x[mask],\,r+\delta'_x[mask],\;x+\delta_y[mask],\,y+\delta'_y[mask])\big) $$

其中四个方向 $(dx,dx',dy,dy')$ 分别对应：

• 左边界右移：$l+1,r$
• 右边界左移：$l,r-1$
• 上边界下移：$x+1,y$
• 下边界上移：$x,y-1$

容斥后，$g$ 表示矩形内“不碰触任何边界”的非空子集的贡献。将所有 $g$ 值存入 $sgvl[l][r][x][y]$。

3. 区间 DP

设 $dp[l][r][S]$ 表示在行区间 $[l,r)$ 内，选择一些恒星，使得这些恒星所在的列集合恰好为 $S$，且这些恒星构成的子图是“不可再分割”的基元（即不能再分成两个独立的矩形子问题）。初始 $dp[l][l][0]=1$。

转移时枚举分割点 $i\in(l,r)$，左边区间 $[l,i)$ 已经确定列集 $T$，右边区间 $[i,r)$ 对应一个连续的列区间 $[t,p+1)$，其贡献为 $sgvl[i][r][t][p+1]$。这样得到的列集为 $T\cup\{t,\dots,p\}$，累加到 $dp[l][r][newS]$。

完成所有分割后，对每个 $S$，找出其最小的列 $i$ 和最大的列 $j$，将 $sgvl[l][r][i][j+1]$ 减去 $dp[l][r][S]$，实现容斥。然后再将所有连续列区间 $[i,t+1)$ 的 $sgvl[l][r][i][t+1]$ 重新加到 $dp[l][r][S]$ 上，最终得到正确的 $dp$ 值。

最后，若区间长度 $>1$，则 $dp[l][r][S]$ 还要加上 $dp[l][r-1][S]$，表示将最后一行单独作为一个块。

4. 全局统计

设 $dp2[l][S]$ 表示只考虑前 $l$ 行（行下标 $0$ 到 $l-1$），且当前列集为 $S$ 的子集个数（即有多少个子集满足其列投影为 $S$）。同时维护 $dpvl2[l][S]$ 表示这些子集的价值之和。

初始化 $dp2[0][0]=1$。按行从左到右扫描：

• 首先，不加任何新行：$dp2[l+1][S] \leftarrow dp2[l][S]$，$dpvl2[l+1][S] \leftarrow dpvl2[l][S]$。
• 然后，对于每个右端点 $r>l$，枚举所有可能的连续列区间 $[i,t+1)$，利用 $sgvl[l][r][i][t+1]$ 将行区间 $[l,r)$ 作为一个整体添加，更新 $dp2[r][newS]$ 和 $dpvl2[r][newS]$。

最终答案即为 $\displaystyle\sum_{S\neq 0} dpvl2[n][S]$。

5. 时间复杂度

预处理 $O(n^4)$，区间 DP $O(n^3\cdot 2^n)$，全局 DP $O(n^2\cdot 2^n)$。由于 $n\le 14$，$2^n\le 16384$，总运算量在可接受范围内。

代码实现

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
string s;
long long dp[15][15][1<<14],vl[200],sgvl[15][15][15][15];
long long dp2[15][1<<14],dpvl2[15][1<<14];
int psum[15][15];
long long getvl(long long l,long long r,long long x,long long y){
    if(l>=r||x>=y)return 0;
    return vl[psum[r][y]-psum[l][y]-psum[r][x]+psum[l][x]];
}
long long f(long long l,long long r,long long x,long long y){
    long long ans=0,i,c,tl,tr,tx,ty;
    for(i=0;i<16;i++)
    {
        c=0;
        tl=l;
        tr=r;
        tx=x;
        ty=y;
        if(i&1)
        {
            c^=1;
            tl++;
        }
        if(i&2)
        {
            c^=1;
            tr--;
        }
        if(i&4)
        {
            c^=1;
            tx++;
        }
        if(i&8)
        {
            c^=1;
            ty--;
        }
        if(c)ans=(ans+mod-getvl(tl,tr,tx,ty))%mod;
        else ans=(ans+getvl(tl,tr,tx,ty))%mod;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T,n,i,j,t,p,l,r,len,cmsk;
    long long ans;
    for(cin>>T;T>0;T--)
    {
        cin>>n;
        vl[0]=0;
        for(i=1;i<=n*n;i++)vl[i]=(vl[i-1]*2+1)%mod;
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=n;j++)psum[i][j]=0;
        }
        for(i=0;i<n;i++)
        {
            cin>>s;
            for(j=0;j<n;j++)psum[i+1][j+1]=s[j]-'0';
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<=n;j++)psum[i+1][j]+=psum[i][j];
        }
        for(i=0;i<=n;i++)
        {
            for(j=0;j<n;j++)psum[i][j+1]+=psum[i][j];
        }
        for(l=0;l<=n;l++)
        {
            for(r=l+1;r<=n;r++)
            {
                for(i=0;i<=n;i++)
                {
                    for(j=i+1;j<=n;j++)sgvl[l][r][i][j]=f(l,r,i,j);
                }
            }
        }
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=n;j++)
            {
                for(t=0;t<(1<<n);t++)dp[i][j][t]=0;
            }
        }
        for(i=0;i<=n;i++)dp[i][i][0]=1;
        for(len=1;len<=n;len++)
        {
            for(l=0;l+len<=n;l++)
            {
                r=l+len;
                for(i=l+1;i<r;i++)
                {
                    for(j=1;j<(1<<n);j++)
                    {
                        for(t=0;t<n;t++)
                        {
                            cmsk=j;
                            for(p=t;p<n&&(j>>p&1^1);p++)
                            {
                                cmsk|=(1<<p);
                                dp[l][r][cmsk]=(dp[l][r][cmsk]+dp[l][i][j]*sgvl[i][r][t][p+1])%mod;
                            }
                        }
                    }
                }
                for(j=1;j<(1<<n);j++)
                {
                    for(i=0;(j>>i&1^1);i++);
                    for(t=n-1;(j>>t&1^1);t--);
                    sgvl[l][r][i][t+1]=(sgvl[l][r][i][t+1]+mod-dp[l][r][j])%mod;
                }
                for(i=0;i<n;i++)
                {
                    cmsk=0;
                    for(t=i;t<n;t++)
                    {
                        cmsk|=(1<<t);
                        dp[l][r][cmsk]=(dp[l][r][cmsk]+sgvl[l][r][i][t+1])%mod;
                    }
                }
                if(len==1)continue;
                for(j=0;j<(1<<n);j++)dp[l][r][j]=(dp[l][r-1][j]+dp[l][r][j])%mod;
            }
        }
        for(i=0;i<=n;i++)
        {
            for(j=0;j<(1<<n);j++)
            {
                dp2[i][j]=0;
                dpvl2[i][j]=0;
            }
        }
        dp2[0][0]=1;
        for(l=0;l<n;l++)
        {
            for(j=0;j<(1<<n);j++)
            {
                dp2[l+1][j]=(dp2[l+1][j]+dp2[l][j])%mod;
                dpvl2[l+1][j]=(dpvl2[l+1][j]+dpvl2[l][j])%mod;
            }
            for(r=l+1;r<=n;r++)
            {
                for(j=0;j<(1<<n);j++)
                {
                    for(i=0;i<n;i++)
                    {
                        cmsk=j;
                        for(t=i;t<n&&(j>>t&1^1);t++)
                        {
                            cmsk|=(1<<t);
                            dp2[r][cmsk]=(dp2[r][cmsk]+dp2[l][j]*sgvl[l][r][i][t+1])%mod;
                            dpvl2[r][cmsk]=(dpvl2[r][cmsk]+(dp2[l][j]+dpvl2[l][j])*sgvl[l][r][i][t+1])%mod;
                        }
                    }
                }
            }
        }
        ans=0;
        for(j=1;j<(1<<n);j++)ans=(ans+dpvl2[n][j])%mod;
        cout<<ans<<'\n';
    }
    return 0;
}

总结

本题利用矩形划分和状压 DP，将原问题转化为组合计数问题，通过容斥和区间合并，高效地求出了所有非空子集的价值之和。核心在于将每个子集的价值分解为若干“不可分割”矩形的贡献，并用 $dp$ 进行累加。