文章目录

杂题 240202-1

发布于

题意

给定 $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() {
}

暂无评论

发表评论