P5857 「SWTR-03」Matrix

一道不错的组合计数题。

题目大意

有一个 \(n\times m\) 的 \(01\) 矩阵，初始时每个元素均为 \(0\)。 有 \(k\) 次操作，每次选择第 \(x\) 行和第 \(y\) 列，将整行元素取反，再将整列元素取反。求 \(k\) 次操作后不同矩阵的种类数，答案对 \(998244353\) 取模。

大体思路

很容易发现，其实行与列的操作是互相独立的，因此本题相当于可重复地取反 \(k\) 行，并且可重复地取反 \(k\) 列。

由于最终某一行（列）有贡献，当且仅当这一行（列）被操作了奇数次，所以我们枚举有 \(i\) 行 \(j\) 列被操作了奇数次，其中 \(i\in [0,\min(n,k)]\)，\(j\in [0,\min(m,k)]\)，并且 \(i,j\) 的奇偶性与 \(k\) 相同。那么，答案即为

\[A=\sum_{i=0}^{\min(n,k)}\sum_{j=0}^{\min(m,k)} \binom n i \binom m j[i,j\equiv k\bmod 2]\pmod {998244353} \]

但是，我们会发现样例中 \(m=n=2\) 的情况便出现了问题。我们思考某一个元素变成 \(1\) 的条件。

如果用 \(0,1\) 表示某一行 \(x\) 被操作偶数次或奇数次，记为 \(I_x\)，那么 \(a_{x,y}=I_x\ \text{xor}\ I_y\)。此时，如果将代表每一行列的 \(01\) 变量 \(I\) 取反，可以证明 \(I_x^{'}\ \text{xor}\ I_y^{'}=I_x\ \text{xor}\ I_y\)，因此这种情况下整个矩阵是相同的。

我们研究何时这种情况会出现。基于行列情况等价，我们讨论行的情况。由于 \(i\) 的奇偶性与 \(k\) 相同，即 \(i\equiv k\pmod 2\)，同时取反后 \(n-i\equiv k\pmod 2\)，两式相加得 \(n\equiv 2k\equiv 0\pmod 2\)。也就是说，\(n,m\) 均为偶数。

同时，重复部分需要满足 \(n-i\le k,i\ge n-k\)，所以 \(i\in [0,n]\cap [n-k,k]\)，\(j\) 同理。我们记这一部分的答案为

\[D=\sum_{i=\max(0,n-k)}^{\min(n,k)}\sum_{j=\max(0,m-k)}^{\min(m,k)} \binom n i \binom m j[i,j\equiv k\bmod 2]\pmod {998244353} \]

由于重复部分在 \(A,D\) 中均被计算两次，最终答案减去重复部分的一半即可，即 \(ans=A-\dfrac D 2\)。

由于 \(998244353\) 为质数，计算 \(\binom n m=\dfrac {n!}{m!(n-m)!}\) 以及使用除法时，利用费马小定理 \(a^{p-1}\equiv 1\)，\(a^{p-2}\equiv a^{-1}\pmod p\) 计算逆元即可。由于 \(n,m\) 同阶，总的时间复杂度为 \(O(n\log p)\)，其中 \(\log p\) 来自于预处理阶乘逆元时快速幂的复杂度。

完整代码

#include 
using namespace std;
#define rep(ii,aa,bb) for(re ll ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair PII;
const int maxn = 2e5 + 5;
const ll mod = 998244353;
namespace IO_ReadWrite {
	#define re register
	#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
	char _buf[1<<21], *p1 = _buf, *p2 = _buf;
	template 
	inline void read(T &x){
		x = 0; re T f=1; re char c = gg;
		while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
		while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
		x *= f;return;
	}
	inline void ReadChar(char &c){
		c = gg;
		while(!isalpha(c)) c = gg;
	}
	template 
	inline void write(T x){
		if(x < 0) putchar('-'), x = -x;
		if(x > 9) write(x/10);
		putchar('0' + x % 10);
	}
	template 
	inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
ll n, m, k, T, inv[maxn], fac[maxn];
inline ll Pow(ll a, ll b) {
	ll res = 1;
	while(b) {
		if(b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return res % mod;
}
inline void init() {
	int N = 2e5;
	fac[0] = inv[0] = 1;
	rep(i, 1, N) {
		fac[i] = (i * fac[i - 1]) % mod;
		inv[i] = Pow(fac[i], mod - 2);
	}
}
inline ll C(ll n, ll m) {
	ll res = fac[n];
	return (((res * inv[m]) % mod) * inv[n - m]) % mod;
}
inline void solve() {
	read(n); read(m); read(k);
	ll c = (k & 1);
	ll sI = 0, sJ = 0;
	for(ll i = c; i <= min(n, k); i += 2) (sI += C(n, i)) %= mod;
	for(ll j = c; j <= min(m, k); j += 2) (sJ += C(m, j)) %= mod;
	ll ans = (sI * sJ) % mod;
	if(!(n & 1) && !(m & 1)) {
		ll dI = 0, dJ = 0;
		for(ll i = max(n - k, 0ll); i <= min(n, k); i += 2) (dI += C(n, i)) %= mod;
		for(ll j = max(m - k, 0ll); j <= min(m, k); j += 2) (dJ += C(m, j)) %= mod;
		ll dlt = ((dI * dJ % mod) * inv[2]) % mod;
		ans = (ans - dlt + mod) % mod;			
	}
	writeln(ans);
}
int main () {
	init();
	read(T);
	while(T --) solve();	
	return 0;
}