下文的点 \(1, 2, 3, 4\) 对应原题面中的 \(S, T, U, V\)。
直接对无向图欧拉回路计数不太好做。考虑给边定向。枚举有 \(i\) 条边是从 \(1\) 到 \(2\) 的。那么 \(2 \to 1\) 有 \(a - i\) 条边。由于这个图必须满足每个点的入度等于出度，设 \(j\) 条 \(2 \to 3\) 的边，\(b - j\) 条 \(3 \to 2\) 的边，那么我们有 \(a - i + j = i + b - j\)。解得 \(j = i + \frac{b - a}{2}\)。同理有 \(k = j + \frac{c - b}{2}\) 条 \(3 \to 4\) 的边，\(l = k + \frac{d - c}{2}\) 条 \(4 \to 1\) 的边。
这样我们就将题目的无向图转化成了有向图。在这个图上做欧拉回路计数。可以考虑 BEST 定理，有向欧拉图的本质不同欧拉回路数量（循环同构视为本质相同，每条边互相区分）为：
\[T \prod\limits_{i = 1}^n (out_i - 1)! \]其中 \(T\) 为图的外向生成树个数（注意到有向欧拉图以每个点为根的外向生成树个数相等），\(out_i\) 为 \(i\) 点的出度。
这题要求欧拉回路从 \(1\) 出发和结束。每一条欧拉回路 \(1\) 都出现了 \(out_1\) 次，把循环同构的加上，所以答案乘上 \(out_1\)。注意这题每条同方向的边互不区分，所以答案乘上 \(\frac{1}{i! (a - i)! j! (b - j)! k! (c - k)! l! (d - l)!}\) 即可。
时间复杂度 \(O(a + b + c + d)\)。
注意判一些无解的情况，比如 \(i, j, k, l\) 不在范围内。
code
// Problem: D - C4
// Contest: AtCoder - AtCoder Grand Contest 051 (Good Bye rng_58 Day 2)
// URL: https://atcoder.jp/contests/agc051/tasks/agc051_d
// Memory Limit: 1024 MB
// Time Limit: 2000 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 maxn = 2000100;
const int N = 2000000;
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;
}
ll A, B, C, D, fac[maxn], ifac[maxn], a[9][9];
inline ll det() {
ll ans = 1;
for (int i = 1; i <= 3; ++i) {
for (int j = i; j <= 3; ++j) {
if (a[j][i]) {
if (i != j) {
swap(a[i], a[j]);
ans = (mod - ans) % mod;
}
break;
}
}
if (!a[i][i]) {
return 0;
}
ans = ans * a[i][i] % mod;
ll t = qpow(a[i][i], mod - 2);
for (int j = i; j <= 3; ++j) {
a[i][j] = a[i][j] * t % mod;
}
for (int j = 1; j <= 3; ++j) {
if (i == j) {
continue;
}
ll t = (mod - a[j][i]) % mod;
for (int k = i + 1; k <= 3; ++k) {
a[j][k] = (a[j][k] + t * a[i][k]) % mod;
}
}
}
return ans;
}
void solve() {
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;
}
scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
if (((B - A) & 1) || ((C - B) & 1) || ((D - C) & 1) || ((A - D) & 1)) {
puts("0");
return;
}
ll ans = 0;
for (int i = 0; i <= A; ++i) {
int j = i + (B - A) / 2;
int k = j + (C - B) / 2;
int l = k + (D - C) / 2;
if (A - i + l != i + D - l || j < 0 || j > B || k < 0 || k > C || l < 0 || l > D || i + D - l == 0 || j + A - i == 0 || k + B - j == 0 || l + C - k == 0) {
continue;
}
mems(a, 0);
a[1][1] = l + A - i;
a[2][2] = i + B - j;
a[3][3] = j + C - k;
a[4][4] = k + D - l;
a[1][2] = (mod - i) % mod;
a[2][1] = (mod - A + i) % mod;
a[2][3] = (mod - j) % mod;
a[3][2] = (mod - B + j) % mod;
a[3][4] = (mod - k) % mod;
a[4][3] = (mod - C + k) % mod;
a[4][1] = (mod - l) % mod;
a[1][4] = (mod - D + l) % mod;
ll res = det() * fac[i + D - l] % mod * fac[j + A - i - 1] % mod * fac[k + B - j - 1] % mod * fac[l + C - k - 1] % mod;
res = res * ifac[i] % mod * ifac[A - i] % mod * ifac[j] % mod * ifac[B - j] % mod * ifac[k] % mod * ifac[C - k] % mod * ifac[l] % mod * ifac[D - l] % mod;
ans = (ans + res) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}