CF1672G Cross Xor

Kubic · 2022-04-24 12:38:10 · 题解

自己编的垃圾做法，感觉好麻烦啊/ll

约定：本文所有 \sum 都是异或和。

显然，一个位置不会被操作 \ge 2 次。

令 x_{i,j} 表示 (i,j) 这个位置有没有被操作过。

可以列出 nm 个如下形式的方程：

a_{i,j}=\sum\limits_{i'=i\lor j'=j} x_{i,j}

但这个矩阵不一定满秩！

于是我们暴力跑线性基来求出这个矩阵的非自由元。

这里先给出一些有关 \mathbb{F}_2 下的矩阵的结论，方便后面阅读：

设 A 为 a_{i,j} 平铺组成的列向量， X 为 x_{i,j} 平铺组成的列向量，V 为方程组所代表的矩阵，\operatorname{size}(V) 表示 V 的大小，\operatorname{rank}(V) 表示 V 的秩。

根据定义，我们有 V\times X=A。

对于固定的 V 和 A，满足 V\times X=A 的 X 有 2^{\operatorname{size}(V)-\operatorname{rank}(V)} 种。

对于固定的 V，满足 V\times X=A 的 A 有 2^{\operatorname{rank}(V)} 种。

分 3 类讨论：

打表可以发现这个方程一定是满秩的！

根据矩阵的结论可以得到任何一种填法都可以对应一组解。直接计算即可。

打表可以发现始终存在一组非自由元长这样（1 代表非自由元）：

分析什么样的 A 是有解的。

首先钦定所有自由元都为 0，这样显然不影响结果。

你可以像我一样对着这一坨东西手算，其实花不了多久也能得出正确结论：

\forall i,j,\sum\limits_{k=1}^m a_{i,k}=\sum\limits_{k=1}^m a_{j,k}

即每一行的异或和都相同。

当然你也可以直接分析操作性质猜出结论，然后回过头再来证明也是比较容易的。

枚举每一行的异或和，我们可以在每一行列出一个关于 a 的方程，共 n 个。

显然这 n 个方程线性无关，只需要判断方程是否有解，如果有解则可以根据矩阵的结论计算解的个数。

打表可以发现始终存在一组非自由元长这样（1 代表非自由元）：

与上一种情况类似，我们可以得出结论：

\forall i,j,\sum\limits_{k=1}^m a_{i,k}=\sum\limits_{k=1}^m a_{j,k},\sum\limits_{k=1}^n a_{k,i}=\sum\limits_{k=1}^n a_{k,j}

即每一行的异或和都相同，每一列的异或和都相同。

又因为 n,m 都是奇数，所以可以得到每一行每一列的异或和都相同。

枚举每一行每一列的异或和，我们可以在每一行每一列列出一个关于 a 的方程，共 n+m 个。

此时就没那么简单了，这 n+m 个方程可能线性相关。

我们考虑选一部分方程使得它们线性相关的条件。

因为每一个变量只会出现两个方程中，所以如果其中一个被选中了，那么另一个也必须被选中，否则就线性无关了。

因此我们考虑建立一张 n+m 个点的图，每个方程对应一个点，如果两个方程同时包含了某一个变量，那么就在这两个方程所对应的点间连一条无向边。

每一个连通块对应一组线性相关的方程，设连通块个数为 c，则矩阵的秩为 n+m-c。最后只需要根据线性相关情况判断方程是否有解，如果有解则可以根据矩阵的结论计算解的个数。

至此，我们已经讨论完了所有情况。

时间复杂度 O(nm)。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 4005
#define MOD 998244353
#define pb push_back
#define pct __builtin_popcount
int n,m;char a[N][N];
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
int add(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
int qPow(int x,int y)
{
    int res=1;
    for(;y;y/=2,x=1ll*x*x%MOD) if(y&1)
        res=1ll*res*x%MOD;return res;
}
namespace Sub1
{
    int t;
    void slv()
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j) t+=a[i][j]=='?';
        printf("%d\n",qPow(2,t));
    }
}
namespace Sub2
{
    int t,fl,cnt[N],w[N];
    void slv()
    {
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
            if(a[i][j]=='?') ++cnt[i];
            else w[i]^=a[i][j]-48;
        for(int i=1;i<=n;++i) if(cnt[i]) t+=cnt[i]-1;
        for(int i=1;i<=n;++i) if(!cnt[i]) fl|=1<<w[i];
        printf("%lld\n",1ll*qPow(2,t)*(2-pct(fl))%MOD);
    }
}
namespace Sub3
{
    int t,fl,cnt[N],w[N];
    void slv()
    {
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
            if(a[i][j]=='?') ++cnt[j];
            else w[j]^=a[i][j]-48;
        for(int i=1;i<=m;++i) if(cnt[i]) t+=cnt[i]-1;
        for(int i=1;i<=m;++i) if(!cnt[i]) fl|=1<<w[i];
        printf("%lld\n",1ll*qPow(2,t)*(2-pct(fl))%MOD);
    }
}
namespace Sub4
{
    int t,fl,w[N];bool vs[N];vector<int> e[N];
    int dfs(int u)
    {
        if(vs[u]) return 0;vs[u]=1;int res=w[u];
        for(auto v:e[u]) res^=dfs(v);return res;
    }
    void slv()
    {
        t=-n-m;
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
            if(a[i][j]=='?') ++t,e[i].pb(n+j),e[n+j].pb(i);
            else w[i]^=a[i][j]-48,w[n+j]^=a[i][j]-48;
        for(int i=1;i<=n+m;++i) if(!vs[i]) fl|=dfs(i),++t;
        for(int i=1;i<=n+m;++i) vs[i]=0,w[i]^=1;
        for(int i=1;i<=n+m;++i) if(!vs[i]) fl|=dfs(i)*2;
        printf("%lld\n",1ll*qPow(2,t)*(2-pct(fl))%MOD);
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%s",a[i]+1);
    if(!(n&1) && !(m&1)) Sub1::slv();
    if(!(n&1) && m&1) Sub2::slv();
    if(n&1 && !(m&1)) Sub3::slv();
    if(n&1 && m&1) Sub4::slv();return 0;
}