KEYENCE20F 题解

· · 题解

Problem Link

检验一个网格能否生成，只要每次删掉所有同色的行列，直到不能删除时判定是否和原网格一致。

通过钦定检验顺序使得每种删除方案恰被计数一次，可以想到依次按行、列、行、列的顺序删除。

那么当我们删除列的时候，相当于钦定当前的每行都不同色，如果当前我们删除的列中有两列不同色，则该限制被满足，递归成对称的问题：在每列不同色的情况删除行。

但如果删除的列都同色（设为黑），那么递归后删除的每行必须都是白色，接下来删除的每列都是黑色，以此类推。

因此对于这两种情况分别定义状态，互相转移即可，边界条件是任何情况下不能删除，即对每个 (a,b)，求有多少（行列可不连续）的 a\times b 子矩阵行列不同色。

注意我们转移的时候已经分配了标号，因此边界情况上要除以 \binom na\times\binom nb。

时间复杂度 \mathcal O(4^n+n^3)。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353;
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
int n,m,a[12][12],b[12][12],r[12],c[12];
ll C[12][12],f1[12][12],g1[12][12],f2[12][12],g2[12][12];
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<12;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1];
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) {
        char o; cin>>o,a[i][j]=o=='#';
        r[i]|=a[i][j]<<j,c[j]|=a[i][j]<<i;
    }
    for(int s=0;s<(1<<n);++s) for(int t=0;t<(1<<m);++t) {
        bool ok=1;
        for(int i=0;i<n;++i) if(s>>i&1) ok&=(r[i]&t)&&(r[i]&t)!=t;
        for(int j=0;j<m;++j) if(t>>j&1) ok&=(c[j]&s)&&(c[j]&s)!=s;
        b[__builtin_popcount(s)][__builtin_popcount(t)]+=ok;
    }
    for(int x=0;x<=n;++x) for(int y=0;y<=m;++y) {
        if(!x||!y) { f2[x][y]=g2[x][y]=1; continue; }
        f1[x][y]=f2[x][y]=g1[x][y]=g2[x][y]=b[x][y]*ksm(C[n][x]*C[m][y])%MOD;
        for(int i=1;i<=x;++i) {
            f1[x][y]=(f1[x][y]+C[x][i]*g1[x-i][y])%MOD;
            f2[x][y]=(f2[x][y]+(((1<<i)-2)*g2[x-i][y]+2*g1[x-i][y])*C[x][i])%MOD;
        }
        for(int i=1;i<=y;++i) {
            g1[x][y]=(g1[x][y]+C[y][i]*f1[x][y-i])%MOD;
            g2[x][y]=(g2[x][y]+(((1<<i)-2)*f2[x][y-i]+2*f1[x][y-i])*C[y][i])%MOD;
        }
    }
    ll ans=0;
    for(int i=0;i<=m;++i) ans=(ans+(1<<i)*f2[n][m-i]*C[m][i])%MOD;
    cout<<ans<<"\n";
    return 0;
}