:::success[闲话]

USACO2026JAN-P 题目考察知识点分布：数学奥林匹克；数学奥林匹克；数学奥林匹克。

做了 SA 所以把 PB 秒了，调了一整场 PC（就是这题）破防了，之后又调了一天过拍了，之后过了。

这题思维难度我觉得是不太高的，代码难度非常高。纯纯大分讨。

---

过了一段时间之后的闲话。

我的复杂度是 $O(\sum X\times\log X)$ 的，与 $R$ 和 $C$ 无关。

后两段会出现对一种常见植物的细节描写。

我草我草我草我草，做复杂了，it is guaranteed that neither the sum of $R$ nor the sum of $C$ over all tests exceeds $10^6$，没看见，当做 n,m<=2e9 做的。

我草我草我草我草我草我草我草，我说怎么人均迅速AK我调那么半天，我是 $O(x\log x)$ 究极复杂做法。

:::

---

我把我觉得重要的地方加粗了。

---

先观察题目要求，任何一个行或列的子段和必须属于 $\{-1,0,1,2\}$，所以整个矩阵上没有任何连续的 -。

观察发现，如果某一行或列存在连续的 +，则其他位置必定是 - 和 + 交替。

*****
*****
-++-+
*****

星号代表还没确定。我们看看我们还能确定什么。

这两个连着的 + 旁边有四个格，其中每一侧有两个相邻的格，则必定有一个是 +。

*****
*+***
-++-+
*****

比如这样。因为没有三个相邻的加号，所以我们可以再确定一个列。

*-***
*+***
-++-+
*-***

减号旁边必定是加号。

+-***
++***
-++-+
*-++*

接着扩充同理，我们发现最后的图形一定是 + 组成若干折线，其他地方时 + 和 - 交替如国象。

同时我们要求每行或每列最多有一个相邻 +，所以这些折线（除端点）向横竖投影都不重合。

因此易证最多有两个折线，折线方向相同。

所以这就说明了答案最大是 $O(n^2)$ 量级，不需要取模。

---

该观察的观察完了，开始分类。

无折线，有两种情况，判一下即可。

折线是主对角线方向，把每个点投影到它的 $x-y$，令 + 为 $o=1$，- 为 $o=0$，反过来也没关系，记录它的期望颜色 $e=(x+y+o)\bmod2$。按 $x-y$ 排序。

扫描 $x-y$ 的过程中，如果我们插入一个折线，会使得能满足的期望颜色翻转，我们分讨这几种情况：插入一条折线（可行当排序后 $e$ 前一半相等，有一半相等），插入两条折线，在相邻两个限制中（可行当 $e$ 唯一），插入两条折线（可行当 $e$ 形如 AAABBBAAA）。记录每种情况的方案数。

这时聪明的你可能发现了插入两条不同位置的折线的其中一个元素可能在排序后的第一个元素前或最后一个元素后，那咋办。我们直接枚举 $a_{1,1},a_{1,m},a_{n,1},a_{n,m}$ 这几个位置的值并钦定它，之后你会发现完全无法在第一个元素前和最后一个元素后插入折线。

折线是辅对角线方向同理，把上面的 $x-y$ 排序改成 $x+y$ 排序即可。

---

细节：

注意折线位置必须是 +，不是单纯的“如果我们插入一个折线，会使得能满足的期望颜色翻转”，所以如果你按照“如果我们插入一个折线，会使得能满足的期望颜色翻转”写代码可能需要根据 $e$ 进行一些加一减一。这是这题最史的部分。

需要对 $n=m=2$ 特判，因为 [[++][++]] 这样的玩意同时算两种折线方向。

---

代码：

你还是自己唔这个题吧，我觉得我的代码对你不可能有帮助。

:::success[代码]

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pii>;

namespace quick_io {
	template<typename... Args>
	ostream& operator<<(ostream& os, const tuple<Args...>& t);
	template<typename T, typename Alloc>
	ostream &operator<<(ostream &A, const vector<T, Alloc> &b);
	template<typename T, typename Alloc>
	ostream &operator<<(ostream &A, const deque<T, Alloc> &b);
	template<typename T1, typename T2>
	ostream &operator<<(ostream &A, const pair<T1, T2> &b);
	template<typename T, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const set<T, Compare, Alloc> &b);
	template<typename T, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const multiset<T, Compare, Alloc> &b);
	template<typename T, typename T2, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const map<T, T2, Compare, Alloc> &b);
	template<typename T, typename T2, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const multimap<T, T2, Compare, Alloc> &b);
	template<typename T, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_set<T, Hash, KeyEqual, Alloc> &b);
	template<typename T, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_multiset<T, Hash, KeyEqual, Alloc> &b);
	template<typename T, typename T2, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_map<T, T2, Hash, KeyEqual, Alloc> &b);
	template<typename T, typename T2, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_multimap<T, T2, Hash, KeyEqual, Alloc> &b);
	template<typename T, typename Alloc>
	ostream &operator<<(ostream &A, const vector<T, Alloc> &b) {
		A << "[";
		for (typename vector<T, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "]";
	}
	template<typename T, typename Alloc>
	ostream &operator<<(ostream &A, const deque<T, Alloc> &b) {
		A << "[";
		for (typename deque<T, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "]";
	}
	template<typename T1, typename T2>
	ostream &operator<<(ostream &A, const pair<T1, T2> &b) {
		return A << '(' << b.first << ',' << b.second << ')';
	}
	template<typename T, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const set<T, Compare, Alloc> &b) {
		A << "{";
		for (typename set<T, Compare, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const multiset<T, Compare, Alloc> &b) {
		A << "{";
		for (typename multiset<T, Compare, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename T2, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const map<T, T2, Compare, Alloc> &b) {
		A << "{";
		for (typename map<T, T2, Compare, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename T2, typename Compare, typename Alloc>
	ostream &operator<<(ostream &A, const multimap<T, T2, Compare, Alloc> &b) {
		A << "{";
		for (typename multimap<T, T2, Compare, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_set<T, Hash, KeyEqual, Alloc> &b) {
		A << "{";
		for (typename unordered_set<T, Hash, KeyEqual, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_multiset<T, Hash, KeyEqual, Alloc> &b) {
		A << "{";
		for (typename unordered_multiset<T, Hash, KeyEqual, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename T2, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_map<T, T2, Hash, KeyEqual, Alloc> &b) {
		A << "{";
		for (typename unordered_map<T, T2, Hash, KeyEqual, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	template<typename T, typename T2, typename Hash, typename KeyEqual, typename Alloc>
	ostream &operator<<(ostream &A, const unordered_multimap<T, T2, Hash, KeyEqual, Alloc> &b) {
		A << "{";
		for (typename unordered_multimap<T, T2, Hash, KeyEqual, Alloc>::const_iterator it = b.begin(); it != b.end(); ++it) {
			if (it != b.begin()) A << ",";
			A << *it;
		}
		return A << "}";
	}
	void print_tuple(ostream&, const tuple<>&) {}
	template<typename T, typename... Rest>
	void print_tuple(ostream& os, const tuple<T, Rest...>& t) {
		os << get<0>(t);
	    if (sizeof...(Rest) > 0) {
			os << ",";
			print_tuple(os, reinterpret_cast<const tuple<Rest...>&>(t));
		}
	}
	template<typename... Args>
	ostream& operator<<(ostream& os, const tuple<Args...>& t) {
		os << "(";
	    print_tuple(os, t);
		return os << ")";
	}
	template<typename T1, typename T2>
	istream &operator>>(istream &A, pair<T1, T2> &b) {
		return A >> b.first >> b.second;
	}
	template<typename T>
	void print_array(T b, T e, string s = " ") {
		while (b != e) {
			cout << *b;
			b++;
			if (b != e) {
				cout << s;
			}
		}
	}
	template<typename T>
	void auto_print(T &b, size_t n, string s = " ") {
		for (size_t i = 1; i < n; i++) {
			cout << b[i] << s;
		}
		cout << b[n];
	}
	template<typename T>
	void auto_print(T &b, string s = " ") {
		for (auto i : b) {
			cout << i << s;
		}
	}
	template<typename T>
	void print_n(T b, size_t n, string s = " ") {
		if (n == 0) return;
		cout << *b;
		for (size_t i = 1; i < n; i++) {
			b++;
			cout << s << *b;
		}
	}
	template<typename T>
	void read_array(T b, T e) {
		while (b != e) {
			cin >> *b;
			b++;
		}
	}
	template<typename T>
	void auto_read(T &b, size_t n) {
		for (size_t i = 1; i <= n; i++) {
			cin >> b[i];
		}
	}
	template<typename T>
	void read_n(T b, size_t n) {
		cin >> *b;
		for (size_t i = 1; i < n; i++) {
			b++;
			cin >> *b;
		}
	}
	template <typename T>
	std::string to_string(const T& value) {
		std::ostringstream oss;
		oss << value;
		return oss.str();
	}
	std::string debug_index() {
		return "";
	}
	template <typename first_t, typename... rest_t>
	std::string debug_index(const first_t& first, const rest_t&... rest) {
		return "[" + to_string(first) + "]" + debug_index(rest...);
	}
	template <typename T>
	auto get_value(T&& arr) -> decltype(std::forward<T>(arr)) {
		return std::forward<T>(arr);
	}
	template <typename T, typename first_t, typename... rest_t>
	auto get_value(T&& arr, first_t&& first, rest_t&&... rest) {
		return get_value(
			std::forward<T>(arr)[std::forward<first_t>(first)],
			std::forward<rest_t>(rest)...
		);
	}
	#define debug(first, ...) #first << debug_index(__VA_ARGS__) << " = " << get_value(first, ##__VA_ARGS__)
	#define spc << ' ' <<
	#undef quick_io_int_length_limit
	#undef quick_io_int_radix_type
	#undef quick_io_length_type
}
using namespace quick_io;

int check(int al, int ar, int at, int bl, int br, int bt, int maxl) {
	// cout << "check " << al spc ar spc at spc bl spc br spc bt spc maxl << endl;
	if (at == -1) {
		int ans1 = check(al, ar, 0, bl, br, bt, maxl);
		int ans2 = check(al, ar, 1, bl, br, bt, maxl);
		// cout << "return " << ans1 << " + " << ans2 << " = " << ans1 + ans2 << endl;
		return ans1 + ans2;
	}
	if (bt == -1) {
		int ans1 = check(al, ar, at, bl, br, 0, maxl);
		int ans2 = check(al, ar, at, bl, br, 1, maxl);
		// cout << "return " << ans1 << " + " << ans2 << " = " << ans1 + ans2 << endl;
		return ans1 + ans2;
	}
	if (ar < al || br < bl) {
		return 0;
	}
	if (al) {
		int ans1 = check(0, ar, at, bl, br, bt, maxl);
		int ans2 = check(0, al - 1, at, bl, br, bt, maxl);
		// cout << "return " << ans1 << " - " << ans2 << " = " << ans1 - ans2 << endl;
		return ans1 - ans2;
	}
	if (bl) {
		int ans1 = check(al, ar, at, 0, br, bt, maxl);
		int ans2 = check(al, ar, at, 0, bl - 1, bt, maxl);
		// cout << "return " << ans1 << " - " << ans2 << " = " << ans1 - ans2 << endl;
		return ans1 - ans2;
	}
	if (at) {
		if (!ar) {
			return 0;
		}
		ar--;
		maxl--;
	}
	if (bt) {
		if (!br) {
			return 0;
		}
		br--;
		maxl--;
	}
	if (maxl < 0) {
		return 0;
	}
	ar /= 2;
	br /= 2;
	maxl /= 2;
	ar = min(ar, maxl);
	br = min(br, maxl);
	maxl = min(maxl, ar + br);
	int d = ar + br - maxl;
	// cout << " = check " << al spc ar spc at spc bl spc br spc bt spc maxl << endl;
	// cout << "return " << (ar + 1) * (br + 1) - d * (d + 1) / 2 << endl;
	return (ar + 1) * (br + 1) - d * (d + 1) / 2;
}
#define MAXN 1000005
int T, n, m, x, maxlen, fx[MAXN], fy[MAXN];
char ft[MAXN];
int type;
int solve(int hl, int hr, vpii hs) {
	// cout << "solve 2" << endl;
	// cout << "[" << hl << ',' << hr << "]" << endl;
	// cout << hs << endl;
	vector<pair<pii, int> > h_change;
	// assert(hs.size() == x);
	for (int i = 1; i < x; i++) {
		if (hs[i - 1].second != hs[i].second) {
			if (hs[i - 1].first == hs[i].first) {
				return 0;
			}
			h_change.push_back({{hs[i - 1].first + ((hs[i - 1].second ^ hs[i - 1].first) & 1),
								 hs[i].first - 1 - ((hs[i].second ^ hs[i].first) & 1)},
								hs[i - 1].second});
			if (h_change.back().first.first > h_change.back().first.second) {
				return 0;
			}
		}
	}
	// cout << h_change << endl;
	int ans = 0;
	if (h_change.size() == 0) {
		for (int i = 1; i < x; i++) {
			ans += check(hs[i - 1].first - hl + 1, hs[i].first - hl, (hs[i - 1].first - hl + 1) & 1,
						 hr - hs[i].first + 1, hr - hs[i - 1].first, (hr - hs[i].first + 1) & 1,
						 maxlen);
			// cout << "i" << i << " ans" << ans << endl;
			// cout << make_pair(hs[i - 1].first - hl + 1, hs[i].first - hl) << endl;
			// cout << make_pair(hr - hs[i].first + 1, hr - hs[i - 1].first) << endl;
			// cout << maxlen << endl;
		}
	} else if (h_change.size() == 1) {
		ans += (h_change[0].first.second - h_change[0].first.first) / 2 + 1;
		// ans += check(0, 0, 0,
					 // hr - h_change[0].first.first, hr - h_change[0].first.second, type ^ (hr & 1),
					 // maxlen);
		// cout << hr - h_change[0].first.first spc hr - h_change[0].first.second spc (type ^ (hr & 1)) << endl;
		// ans += check(h_change[0].first.first - hl + 1, h_change[0].first.second - hl + 1, type ^ 1 ^ (hl & 1),
					 // 0, 0, 0,
					 // maxlen);
		// cout << h_change[0].first.first - hl + 1 spc h_change[0].first.second - hl + 1 spc (type ^ (hr & 1)) << endl;
	} else if (h_change.size() == 2) {
		ans += check(h_change[0].first.first - hl + 1, h_change[0].first.second - hl + 1, (h_change[0].first.first - hl + 1) & 1,
					 hr - h_change[1].first.second, hr - h_change[1].first.first, (hr - h_change[1].first.first) & 1,
					 maxlen);
		// cout << vi{h_change[0].first.first - hl + 1, h_change[0].first.second - hl + 1} << endl;
		// cout << vi{hr - h_change[1].first.first, hr - h_change[1].first.second} << endl;
		// cout << maxlen << endl;
		// cout << h_change[0].first.first - hl + 1 << ',' << hr - h_change[1].first.first << endl;
	}
	// cout << "solve return " << ans << endl;
	return ans;
}
int solve() {
	bool flag_all[2]{1, 1};
	vpii hs, cs;
	// cout << "solve :" << endl;
	// cout << debug(n) << endl;
	// cout << debug(m) << endl;
	for (int i = 1; i <= x; i++) {
		// cout << i << ' ' << ft[i] << ' ' << fx[i] << ' ' << fy[i] << ' ' << ((fx[i] ^ fy[i] ^ (ft[i] == '+' ? 0 : 1)) & 1) << endl;
		flag_all[(fx[i] ^ fy[i] ^ (ft[i] == '+' ? 0 : 1)) & 1] &= 0;
		hs.push_back({fx[i] + fy[i], (fx[i] ^ fy[i] ^ (ft[i] == '+' ? 0 : 1)) & 1});
		cs.push_back({fx[i] - fy[i], (fx[i] ^ fy[i] ^ (ft[i] == '+' ? 0 : 1)) & 1});
		type = (fx[i] ^ fy[i] ^ (ft[i] == '+' ? 0 : 1)) & 1;
	}
	int cl = 1 - m, cr = n - 1;
	int hl = 2, hr = n + m;
	int ans = flag_all[0] + flag_all[1];
	sort(all(hs));
	sort(all(cs));
	// vector<pair<pii, int> > h_change, c_change;
	// bool can_h = 1, can_c = 1;
	// for (int i = 1; i < x; i++) {
		// if (hs[i - 1].second != hs[i].second) {
			// if (hs[i - 1].first == hs[i].first) {
				// // cout << "NULL1" << endl;
				// // cout << hs << endl;
				// // return 0;
				// can_h = 0;
			// }
			// h_change.push_back({{hs[i - 1].first + ((hs[i - 1].second ^ hs[i - 1].first) & 1), hs[i].first - 1 - ((hs[i].second ^ hs[i].first) & 1)}, hs[i - 1].second});
		// }
	// }
	// if (can_h) {
		// ans += solve(hl, hr, hs);
	// }
	// if (can_c) {
		// ans += solve(cl, cr, cs);
	// }
	ans += solve(hl, hr, hs);
	if (n != 1 && m != 1) {
		ans += solve(cl, cr, cs);
	}
	return ans;
}
signed main() {
	cin >> T;
	while (T--) {
		cin >> n >> m >> x;
		maxlen = min(n, m);
		for (int i = 1; i <= x; i++) {
			cin >> ft[i] >> fx[i] >> fy[i];
			// cout << i << ' ' << ft[i] << ' ' << fx[i] << ' ' << fy[i] << endl;
		}
		int ans = 0;
		x += 4;
		fx[x - 3] = 1; fy[x - 3] = 1;
		fx[x - 2] = n; fy[x - 2] = 1;
		fx[x - 1] = 1; fy[x - 1] = m;
		fx[x - 0] = n; fy[x - 0] = m;
		bool flagflag = 1;
		// for (char i1 : {'-', '+'}) {
		for (char i1 : {'+', '-'}) {
			ft[x - 3] = i1;
			// for (char i2 : {'-', '+'}) {
			for (char i2 : {'+', '-'}) {
				ft[x - 2] = i2;
				// for (char i3 : {'-', '+'}) {
				for (char i3 : {'+', '-'}) {
					ft[x - 1] = i3;
					// for (char i4 : {'-', '+'}) {
					for (char i4 : {'+', '-'}) {
						ft[x - 0] = i4;
						int nowans = solve();
						if (i1 + i2 + i3 + i4 == 4 * '+' && n == 2 && m == 2) {
							nowans /= 2;
						}
						ans += nowans;
						// cout << i1 << i2 << i3 << i4 << nowans << endl;
					}
				}
			}
		}
		cout << ans << endl;
		// if (x == 0) {
			// cout << 2
				 // + (check(1, m, 0, 1, m & 1 ? , -1, maxlen)
				  // + check(1, m, -1, 1, m, -1, maxlen)) * 2 + check(0, 0, -1, 1, m, -1, maxlen) * 4 << endl;
			// continue;
		// }
		// int cl = 1 - n, cr = 1 + m;
		// int hl = 2, hr = n + m;
		// vpii cs{{cl - 1, 1}, {cr + 1, 1}}, hs{{hl - 1, 1}, {hr + 1, 1}};
		// bool all0 = 1, all1 = 1;
		// for (int i = 1, t, X, Y; i <= x; i++) {
			// cin >> t >> X >> Y;
			// cs.push_back({X - Y, (X ^ Y ^ (t == '+' ? 1 : 0)) & 1});
			// hs.push_back({X + Y, (X ^ Y ^ (t == '+' ? 1 : 0)) & 1});
			// if ((X ^ Y ^ (t == '+' ? 1 : 0)) & 1) {
				// all0 = 0;
			// } else {
				// all1 = 0;
			// }
			// // 若 (1,1) 是 -，second 是 1 就得被翻
		// }
		// sort(all(cs));
		// sort(all(hs));
		// int ans = all0 + all1;
		// for (int i = 1; i <= n; i++) {
// 			
		// }
	}
	return 0;
}

/*

每行和每列最多只有一对 ++ 相邻，其他位置相邻元素不同
-+-+-++-
+-+-+-++
++-+-+-+
-++-+-+-
+-++-+-+
-+-++-+-
+-+-++-+

手完发现只可能国象棋盘，但是是若干 + 斜线宽度是 2 这样的斜线最多有两个。

若无这样的斜线，那就只有两种情况，很好解决

若有一条这样的斜线，那就有一个分割线，分成两个国象，对于两种方向分讨一下，之后统计一下。

若有两条这样的斜线，相当于挖去两个三角，分讨一下。

好像一条线加俩哨兵可以当做两条线考虑。不对，因为需要保证分界线之间的距离是偶数。

定义分界线的位置为其割走的三角的边界的 x+y

处于割走的图形中的 + 希望分界线位置和自己一样。

*/

:::

Analysis by Nelson Huang)

Subtask 1:

Let's first determine which rows have all contiguous subsegment sums between $-1$ and $2$. We note

• There can never be two - in a row.
• There can be at most two + in a row.

Let's analyze the number of ++ in the row. We observe that there can only be at most one occurrence of ++ in a row. Otherwise, we can take a contiguous subsegment between two occurrences of ++,

+ + - ... - + +

which has a sum of $3$.

Then, we can try all such grids and determine which ones are consistent with Farmer John's memory, which can be done in $O(\max(R, C))$ time.

Full solution:

Now, we have multiple rows and columns. Let's take a row that has an occurrence of ++:

- + - + + - + -

Now, let's analyze the possible rows that can be under this row. We cannot have two - in a row, so all cells under - must be +:

- + - + + - + - + * + * * + * +

Since we can only have one occurrence of ++ in the second row and we cannot have two - in a row, we only have two possibilities for this row:

- + - + + - + - + - + + - + - +

and

- + - + + - + - + - + - + + - +

The one exception is when $R=2$ and $C=2$. In that case, we can also have

+ + + +

Let's assume the lower ++ is to the left of the upper ++. Now, the only possibility for the next row is

- + - + + - + - + - + + - + - + - + - + + - + -

We extend downwards until the ++ hits the left or bottom of the grid.

- + - + + - + - + - + + - + - + - + - + + - + - + + - + + - + - + - + - + + - +

A similar analysis holds for upwards. Call this sequence of ++ a chain.

We observe that there cannot be two chains in opposite directions. To prove this, let's try to construct two chains in opposite directions. First, we construct the chain going down and to the left, like in this example:

* * * * * * * * * *
* + + * * * * * * *
* + * + * * * * * *
* + * * + * * * * *
* + * * * + * * * *
* + * * * * + * * *
* + * * * * * + * *
* + * * * * * * + *
* + * * * * * * * +
* * * * * * * * * *

There are two cases for the chain going down and to the right:

• The chain goes from the left to the bottom of the grid: Then, there will exist multiple ++ in the first few columns, like in this example:

  * * + * * * * * * *
  * + + * * * * * * *
  + * + * * * * * * *
  * + * + * * * * * *
  * * + * + * * * * *
  * * * + * + * * * *
  * * * * + * + * * *
  * * * * * + * + * *
  * * * * * * + * + *
  * * * * * * * + * *
  

• The chain goes from the top to either the bottom or right: Then, there will exist multiple ++ in the first few rows, like in this example:

  * * + + + + + * * *
  * + + * * * * + * *
  + * + * * * * * + *
  * + * + * * * * * +
  * * + * + * * * * *
  * * * + * + * * * *
  * * * * + * + * * *
  * * * * * + * + * *
  * * * * * * + * + *
  * * * * * * * + * *
  

Now, WLOG, the chains go down and to the left. We can solve the other case by reversing the columns.

Next, we observe that the values in each diagonal going left and down are the same. Consider if one diagonal has

  +
-

Then, the surrounding values must be

+ +
- +

However, this does not follow the additional condition that the lower ++ is to the left of the upper ++, as the lower left cell is -. The other case of

+
-

is similar.

We can index the diagonals from $1$ to $R+C-1$, where cell $(i, j)$ corresponds to diagonal $i+j-1$. Notice that without any ++ chain, the values of the diagonals alternate between + and -, but a ++ chain creates two diagonals with values + and +, effectively flipping the values of the following diagonals. Denote the position of a ++ chain as the diagonal the right + is in: the first diagonal whose parity is flipped relative to the alternating pattern.

With this observation, we can now determine the condition for placing multiple chains in a grid. Let's have the chain with the earliest position at position $d$, and assume $C \ge R$:

* * + * * * * * * *
* + + * * * * * * *
* + * + * * * * * *
* + * * + * * * * *
* + * * * + * * * *
* + * * * * + * * *
* + * * * * * + * *
* + * * * * * * + *
* + * * * * * * * +
* * * * * * * * * *

We cannot have more than one ++ in a single row or column, so the minimum position of the following chain is $d+C-1$, constructed as follows:

* * + * * * * * * *
* + + * * * * * * *
* + * + * * * * * *
* + * * + * * * * *
* + * * * + * * * *
* + * * * * + * * *
* + * * * * * + * *
* + * * * * * * + *
* + * * * * * * * +
* * * * * * * * + +

However, the diagonals in between must alternate between + and -. This means that when $C \equiv 1 \pmod 2$, the minimum position of the right chain is $d+C$. This also means that only every other diagonal after the minimum position is a valid position of the right chain.

In general, the minimum position of the following chain when the previous chain is at position $d$ is

• $d + \max(R, C) - 1$ when $\max(R, C) \equiv 0 \pmod 2$,
• $d + \max(R, C)$ otherwise.

In particular, if $d > \min(R, C)$, then there cannot be any further following chains. This also means that there can be at most two chains in a grid, because $d + \max(R, C) - 1 > \min(R, C)$ (note that $d \ge 2$).

Now, let's analyze which grids are consistent with Farmer John's memory.

For simplicity, fix the values of the first and last diagonals. This will reduce the number of cases. Then, let's analyze the diagonals that have existing values in them and take consecutive pairs of them. For a pair:

• If we cannot insert an alternating sequence of + and - between the two diagonals, there must be exactly $1$ chain between them.
• Otherwise, there must be either $0$ or $2$ chains between them.

This means,

• If there are $0$ of the first type of pair, then there are either $0$ chains or both chains are between two consecutive diagonals with values.
• If there is $1$ of the first type of pair, then there is exactly $1$ chain between those two diagonals and no chains anywhere else.
• If there are $2$ of the first type of pair, then there is $1$ chain between the diagonals of the first pair and $1$ chain between the diagonals of the second pair.
• If there are $3$ or more of the first type of pair, the answer is $0$.

For the cases where we have two chains, we can iterate through the position of the left chain and count the number of possible positions for the right chain.

Beware of the edge cases of $\min(R, C) = 1$ and $R = C = 2$. This solution takes $O(R + C + X)$ time.

Nelson's code:

#include <bits/stdc++.h>
using i64 = long long;
struct Cell {
    int v, r, c;
};
void tc() {
    int r, c, x;
    std::cin >> r >> c >> x;
    std::vector<Cell> cl(x);
    for (auto& [v, ri, ci] : cl) {
        char cc;
        std::cin >> cc >> ri >> ci;
        v = cc == '+';
        --ri;
        --ci;
    }
    if (r == 1 && c == 1) {
        if (x == 1)
            std::cout << 1 << '\n';
        else
            std::cout << 2 << '\n';
        return;
    }
    auto get_mi_rb = [&](int d) {
        int mx = std::max(r, c);
        if (mx % 2 == 0)
            return d + mx - 1;
        return d + mx;
    };
    auto comp = [&](int mi, int rb) {
        if (mi > rb)
            return 0;
        return (rb - mi) / 2 + 1;
    };
    i64 ans = 0;
    auto solve = [&](bool z) {
        std::vector vals(r + c - 1, -1);
        for (auto [v, ri, ci] : cl) {
            if (vals[ri + ci] == -1)
                vals[ri + ci] = v;
            else if (vals[ri + ci] != v)
                return;
        }
        bool ff = vals[0] == -1, fl = vals[r + c - 2] == -1;
        for (int fval : {0, 1}) {
            if (!ff && vals[0] != fval)
                continue;
            vals[0] = fval;
            for (int lval : {0, 1}) {
                if (!fl && vals[r + c - 2] != lval)
                    continue;
                vals[r + c - 2] = lval;
                std::vector<int> d;
                for (int i = 0; i < r + c - 1; ++i) {
                    if (vals[i] != -1)
                        d.push_back(i);
                }
                std::pair i1{-1, -1}, i2{-1, -1};
                bool g = true;
                for (int i = 0; i < (int)d.size() - 1; ++i) {
                    int lb = d[i], rb = d[i + 1];
                    if ((vals[lb] ^ vals[rb]) != (rb - lb) % 2) {
                        if (i1.first == -1)
                            i1 = {lb, rb};
                        else if (i2.first == -1)
                            i2 = {lb, rb};
                        else {
                            g = false;
                            break;
                        }
                    }
                }
                if (!g)
                    continue;
                if (i1.first == -1) {
                    if (!z)
                        ++ans;
                    for (int i = 0; i < (int)d.size() - 1; ++i) {
                        int L = d[i], R = d[i + 1];
                        for (int lb = vals[L] == 1 ? L + 1 : L + 2; get_mi_rb(lb) <= R; lb += 2)
                            ans += comp(get_mi_rb(lb), R);
                    }
                } else if (i2.first == -1) {
                    auto [L, R] = i1;
                    if (vals[L] == 1)
                        ans += comp(L + 1, R);
                    else
                        ans += comp(L + 2, R);
                } else {
                    auto [l1, r1] = i1;
                    auto [l2, r2] = i2;
                    for (int lb = vals[l1] == 1 ? l1 + 1 : l1 + 2; lb <= r1; lb += 2) {
                        int rb = std::max(get_mi_rb(lb), vals[l2] == 1 ? l2 + 1 : l2 + 2);
                        ans += comp(rb, r2);
                    }
                }
            }
        }
    };
    solve(true);
    if (std::min(r, c) > 1) {
        for (auto& [v, ri, ci] : cl)
            ci = c - 1 - ci;
        solve(false);
    }
    if (r == 2 && c == 2) {
        bool g = true;
        for (auto [v, ri, ci] : cl) {
            if (v == 0) {
                g = false;
                break;
            }
        }
        if (g)
            --ans;
    }
    std::cout << ans << '\n';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--)
        tc();
}