\(20240303\) 随机好题

CF40E

引理1：若答案不为 \(0\)，则 \(n, m\) 同奇偶。

证明：每行、列都是 \(1\)，那么考虑把每个数乘起来。有 \((-1)^n = (-1)^m\)。所以 \(n \equiv m (\bmod 2)\)

引理2：在引理1 的条件下，若已确定所有列满足条件，一行之外的所有行也满足条件，那么该行也满足。证明同上。

一道比较好的组合计数。首先观察题目，我相信大部分人应该都注意到了 \(0 \le k < \max \{ n, m \}\)。我们来思考这意味着什么。

我们假设 \(n > m\)，那么至少有一行，一个数字也不填。假设其他行填完了，满足条件。那么剩下的也肯定满足：首先每列可以通过这一行来调整是他都变成 \(-1\)，然后通过引理2可以证明改行也满足。

于是我们只用考虑除了哪一行之外的其他行的方法数的乘积。所以说我们就有每一行的填法是 \(2^{m - \text{已填的个数} - 1}\)。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e3 + 5;
int n, m, k, flag, Mod, mex, ans, qpow[N], cnt[N], val[N];

signed main(){
	cin >> n >> m >> k;
	if(k >= n) flag = 1, swap(n, m);
	for(int i = 1; i <= k; i++){
		int x, y, z;
		cin >> x >> y >> z;
		if(flag) swap(x, y);
		cnt[x]++;
		val[x] = val[x] == 0 ? z : val[x] * z;
	}
	mex = 1; while(cnt[mex]) mex++;
	cin >> Mod;
	
	qpow[0] = 1;
	for(int i = 1; i <= max(n, m); i++) qpow[i] = qpow[i - 1] * 2 % Mod;
	ans = !(((n & 1) ^ (m & 1)) & 1);
	for(int i = 1; i <= n; i++){
		if(i == mex) continue;
		if(cnt[i] == m && val[i] == 1) ans = 0;
		if(cnt[i] ^ m) ans = (ans * qpow[m - cnt[i] - 1]) % Mod;
	}
	cout << ans << endl;
	return 0;
}