题解 P5159 【WD与矩阵】
ezoixx130
2018-12-31 12:06:01
### 题意：
题意很简单，就是问有多少个 $n$ 行 $m$ 列的 $01$ 矩阵的每行和每列的异或和均为 $0$。
### 题解：
首先我们知道 $n-1$ 行 $m-1$ 列的 $01$ 矩阵的个数是 $2^{(n-1)(m-1)}$。
然后考虑对一个 $n-1$ 行 $m-1$ 列的 $01$ 矩阵求每行和每列的异或和，并且把异或和放到每行或每列的末尾。
这样我们就得到了一个 $n$ 行 $m$ 列的 $01$ 矩阵，特别地，第 $n$ 行 $m$ 列填上原本 $n-1$ 行 $m-1$ 列的 $01$ 矩阵中的所有数的异或和。
根据异或的性质不难得到，这个 $n$ 行 $m$ 列的 $01$ 矩阵的每行和每列的异或和均为 $0$。也就是说，这个矩阵符合题目要求。
上面我们证明了，每个 $n-1$ 行 $m-1$ 列的 $01$ 矩阵对应一个每行和每列的异或和均为 $0$ 的 $n$ 行 $m$ 列的 $01$ 矩阵。
那么有没有符合题意的 $n$ 行 $m$ 列的 $01$ 矩阵，它不被任何一个 $n-1$ 行 $m-1$ 列的 $01$ 矩阵所对应呢？
显然没有，因为每个符合题意的 $n$ 行 $m$ 列的 $01$ 矩阵，第 $n$ 行的每个数都等于它所在列的其它数的异或和，第 $m$ 列的每个数也都等于它所在行的其他数的异或和，所以它一定能被一个 $n-1$ 行 $m-1$ 列的 $01$ 矩阵所对应。
于是 $n-1$ 行 $m-1$ 列的 $01$ 矩阵与符合题意的 $n$ 行 $m$ 列的 $01$ 矩阵是一一对应的，所以个数相等，均为 $2^{(n-1)(m-1)}$。
快速幂求答案即可。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
int qpow(int a,long long b)
{
int res=1;
while(b)
{
if(b&1)res=(long long)res*a%mod;
a=(long long)a*a%mod;
b>>=1;
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
printf("%d\n",qpow(2,(long long)(n-1)*(m-1)));
}
}
```