题意
给定 $n, m$ 和长度都为 $m$ 的数组 $L$ 和 $R$。
要求选出 $m$ 个数,第 $i$ 个数在 $\left[L_i, R_i\right]$ 里,使得他们的和为 $n$。
求出方案数对 $998244353$ 取模的结果。两种方案不同,当且仅当某个数的值不同。
$1 \leq n \leq 10^9, 1 \leq m \leq 20, 0 \leq L_i \leq R_i \leq 10^9$
题解
首先,我们可以把 $n$ 减去 $\sum L_i$,每个 $R_i$ 也减去 $L_i$,这样,每个数的值就可以在 $\left[0, R_i\right]$ 里选了。
同时,$m \leq 20$ 给了我们启发,可以容斥哪些数不在范围内。容斥之后的问题变成了:在剩下的数中,随便选值(即可以超出范围),但要求最终总和为 $t = n - \sum\limits_{k\ was\ selected} \left(R_k + 1\right)$ 的方案数。这相当于是选择一些非负整数使他们的和为 $t$,又相当于是选择一些正整数使他们的和为 $t + n$,隔板法计算。具体看代码就懂了。
还有就是在求组合数的时候不能暴力算阶乘($n = 10^9$),但 $m \leq 20$,所以使用展开乘的方法计算:
tp binom(tp n, tp m) {
tp tar = 1;
for (tp i = 1; i <= m; ++i) tar = tar * (n - i + 1) % mod * inv[i] % mod;
return tar;
}
代码
constexpr tp mod = 998244353;
constexpr tp inv[] { 0, 1, 499122177, 332748118, 748683265, 598946612, 166374059, 855638017, 873463809, 443664157, 299473306, 272248460, 582309206, 460728163, 926941185, 865145106, 935854081, 939524097, 720954255, 105078353, 149736653 };
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp m, n, tar = 0; bin >> m >> n;
vector<tp> a(m);
for (tp i = 0; i < m; ++i) {
tp l, r; bin >> l >> r;
n -= l;
a[i] = r - l;
}
for (tp i = 0; i < (1ll << m); ++i) {
tp sum = n, f = 1;
for (tp j = 0; j < m; ++j) {
if (i >> j & 1) { sum -= a[j] + 1; f *= -1; }
}
if (sum < 0) continue;
dbg(i, sum, binom(m + sum - 1, m - 1));
tar = (tar + f * binom(m + sum - 1, m - 1) + mod) % mod;
}
bin << tar << '\n';
}
void MIST() {
}