什么 [ABC336G] 16 Integers 究极弱化版。
把元素 \(1\) 看成 \(01\)，元素 \(2\) 看成 \(10\)，元素 \(3\) 看成 \(11\)，元素 \(4\) 看成 \(00\)。则转化为统计长度为 \(2\) 的子串 \(xy\) 出现次数为 \(c_{xy}\) 的 \(01\) 串个数。
把子串 \(xy\) 看成 \(x \to y\) 的一条有向边，那么这是一个点数为 \(2\) 的欧拉路径计数问题，可以 BEST 定理解决，但是不需要。
有解的必要条件是 \(|c_{01} - c_{10}| \le 1\)。若 \(c_{01} = c_{10}\) 那么 \(01\) 串开头和结尾的字符相同。若以 \(0\) 开头和结尾，相当于把 \(c_{00} + c_{01} + 1\) 个 \(0\) 分成 \(c_{01} + 1\) 份，\(c_{10} + c_{11}\) 个 \(1\) 分成 \(c_{c10}\) 份，每份非空，根据插板法可得方案数为 \(\binom{c_{00} + c_{01}}{c_{01}} \binom{c_{10} + c_{11} - 1}{c_{10} - 1}\)。以 \(1\) 开头和结尾类似。
若 \(c_{01} = c_{10} + 1\)，那么以 \(0\) 开头，以 \(1\) 结尾。相当于把 \(c_{00} + c_{01}\) 个 \(0\) 分成 \(c_{01}\) 份，\(c_{11} + c_{01}\) 个 \(1\) 分成 \(c_{01}\) 份，方案数为 \(\binom{c_{00} + c_{01} - 1}{c_{01} - 1} \binom{c_{11} + c_{01} - 1}{c_{01} - 1}\)。
\(c_{10} = c_{01} + 1\) 的情况是类似的。注意特判 \(c_{10} = c_{01} = 0\)，这种情况只能是全 \(0\) 或全 \(1\)，所以 \(c_{00}\) 和 \(c_{11}\) 不能都非 \(0\)。
时间复杂度 \(O(T + \sum c_i)\)。
code
// Problem: G. One-Dimensional Puzzle
// Contest: Codeforces - Codeforces Round 925 (Div. 3)
// URL: https://codeforces.com/contest/1931/problem/G
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int N = 4000000;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
int c00, c01, c10, c11;
ll fac[N + 5], ifac[N + 5];
inline void init() {
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 1;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%d%d%d%d", &c01, &c10, &c11, &c00);
if (abs(c01 - c10) >= 2) {
puts("0");
return;
}
if (c01 == 0 && c10 == 0) {
puts(((c00 ? 1 : 0) + (c11 ? 1 : 0)) == 2 ? "0" : "1");
return;
}
if (c01 == c10) {
printf("%lld\n", (C(c11 + c10 - 1, c10 - 1) * C(c01 + c00, c01) + C(c11 + c10, c10) * C(c01 + c00 - 1, c01 - 1)) % mod);
} else if (c01 == c10 + 1) {
printf("%lld\n", C(c11 + c01 - 1, c01 - 1) * C(c01 + c00 - 1, c01 - 1) % mod);
} else {
printf("%lld\n", C(c11 + c10 - 1, c10 - 1) * C(c10 + c00 - 1, c10 - 1) % mod);
}
}
int main() {
init();
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}