考虑不要求每个盒子至少放一个球，答案即为 \(\sum\limits_{i=0}^A \binom{n}{i} \times \sum\limits_{i=0}^B \binom{n}{i} \times \sum\limits_{i=0}^C \binom{n}{i}\)。
加上这个条件，考虑容斥，钦定 \(i\) 个盒子不能放球，其他随意，则答案为 \(\sum\limits_{i=0}^n (-1)^i \binom{n}{i} \sum\limits_{j=0}^A \binom{n-i}{j} \times \sum\limits_{j=0}^B \binom{n-i}{j} \times \sum\limits_{j=0}^C \binom{n-i}{j}\)。
似乎没有快速算 \(\sum\limits_{i=0}^m \binom{n}{i}\) 的方法，但是观察发现式子中 \(m\) 不变，\(n\) 每次减一，考虑递推。设 \(f_i = \sum\limits_{j=0}^A \binom{i}{j}\)，则根据 \(\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}\)，可得 \(f_i = \frac{f_{i+1} + \binom{i}{A}}{2}\)。按照相同的方法递推出 \(g_i = \sum\limits_{j=0}^B \binom{i}{j}\) 和 \(h_i = \sum\limits_{j=0}^C \binom{i}{j}\)，答案即为 \(\sum\limits_{i=0}^n (-1)^i \binom{n}{i} f_{n-i} g_{n-i} h_{n-i}\)。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 10000100;
const int N = 10000000;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
ll n, X, Y, Z, fac[maxn], ifac[maxn], f[maxn], g[maxn], h[maxn];
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;
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld%lld%lld%lld", &n, &X, &Y, &Z);
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;
}
for (int i = 0; i <= X; ++i) {
f[n] = (f[n] + C(n, i)) % mod;
}
for (int i = n - 1; ~i; --i) {
f[i] = (f[i + 1] + C(i, X)) % mod * inv2 % mod;
}
for (int i = 0; i <= Y; ++i) {
g[n] = (g[n] + C(n, i)) % mod;
}
for (int i = n - 1; ~i; --i) {
g[i] = (g[i + 1] + C(i, Y)) % mod * inv2 % mod;
}
for (int i = 0; i <= Z; ++i) {
h[n] = (h[n] + C(n, i)) % mod;
}
for (int i = n - 1; ~i; --i) {
h[i] = (h[i + 1] + C(i, Z)) % mod * inv2 % mod;
}
ll ans = 0;
for (int i = 0; i <= n; ++i) {
ans = (ans + ((i & 1) ? mod - 1 : 1) * C(n, i) % mod * f[n - i] % mod * g[n - i] % mod * h[n - i] % mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}