Solution -「ABC 215G」Colorful Candies 2

首页

关于

笔记

文章

友链

Solution -「ABC 215G」Colorful Candies 2

cirnovsky / Aug 23, 2021

link。

称题目中的 $c_i$ 为 $a_i$ ，令 $c_i$ 为第 $i$ 种颜色的出现次数，令 $C$ 为颜色总数。固定 $k$ ，令 $t_i=1$ ，如果颜色 $i$ 被选择了一次及以上，否则为 $0$ ，则答案为 $\textbf{E}(\sum t_i)=\sum\textbf{E}(t_i)=\sum\frac{\binom{n}{k}-\binom{n-c_i}{k}}{\binom{n}{k}}$ 。

对于一个固定的 $k$ ，上式的取值只取决于 $c_i$ 的大小，令 $s_x$ 为 $c_i=x$ 的 $i$ 的数量。则答案写为 $\sum s_x\times\frac{\binom{n}{k}-\binom{n-x}{k}}{\binom{n}{k}}$ 。

分析复杂度， $n=\sum i\times s_i$ ，因此单次计算最劣 $\Theta(\sqrt n)$ 。

#include <bits/stdc++.h>

#include <atcoder/modint>
using mint = atcoder::modint998244353;
mint fac[50100], ifac[50100];
void preComb(int n) {
  fac[0] = ifac[0] = mint::raw(1);
  for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i;
  ifac[n] = fac[n].inv();
  for (int i = n - 1; i; --i) ifac[i] = ifac[i + 1] * (i + 1);
}
mint C(int n, int k) {
  if (n < k) return 0;
  return fac[n] * ifac[n - k] * ifac[k];
}
int c[50100], s[50100], n, a[50100];
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  std::cin >> n;
  preComb(n);
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  std::vector<int> pri(a + 1, a + n + 1);
  std::sort(pri.begin(), pri.end());
  pri.erase(std::unique(pri.begin(), pri.end()), pri.end());
  int C = static_cast<int>(pri.size());
  for (int i = 1; i <= n; ++i)
    a[i] = std::lower_bound(pri.begin(), pri.end(), a[i]) - pri.begin() + 1;
  for (int i = 1; i <= n; ++i) ++c[a[i]];
  for (int i = 1; i <= C; ++i) ++s[c[i]];
  std::vector<int> vec;
  for (int i = 1; i <= n; ++i) {
    if (s[i]) vec.emplace_back(i);
  }
  for (int k = 1; k <= n; ++k) {
    mint res = 0;
    for (int x : vec) res += s[x] * (::C(n, k) - ::C(n - x, k));
    res *= ::C(n, k).inv();
    std::cout << res.val() << '\n';
  }
  return 0;
}