ABC215-G Colorful Candies 2
(Test/AtCoder/abc215_g.test.cpp)

• View this file on GitHub
• Last update: 2025-05-09 01:17:18+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc215/submissions/65595540
• Link: https://atcoder.jp/contests/abc215/tasks/abc215_g

$C$ は座圧されているものとし、 種類 $i (1 \le i \le N)$ のキャンディの個数が $n_{i}$ であるとする。

期待値の線型性より、 $K$ 個のキャンディを選択したとき、少なくとも $1$ 個以上の種類 $i$ のキャンディを取る確率を $i = 1, 2, \dots, N$ について計算できれば良い。

余事象を考えると、 $K$ に対して解は $\frac{1}{\binom{N}{K}}\sum_{i = 1}^{N}(\binom{N}{K}-\binom{N-n_{i}}{K})$ である。

$=N-\frac{1}{\binom{N}{K}}\sum_{i=1}^{N}\binom{N-n_{i}}{K}$

結局の所 $\sum_{i=1}^{N}\binom{N-n_{i}}{K}$ が全ての $K$ で計算できれば良い。

$f(x) = \sum_{i = 0}^{N} \sum_{j = 1}^{N}\binom{N-n_{j}}{i}x^{i}$ とすると…

$= \sum_{j = 1}^{N} \sum_{i = 0}^{N} \binom{N-n_{j}}{i}x^{i} = \sum_{j = 1}^{N} (1+x)^{N-n_{j}}$ (二項定理)

よって $g(x) = \sum_{j = 1}^{N} x^{N-n_{j}}$ をPolynomial Taylor Shiftすることで $f(x)$ の係数列が $O(N\log N)$ で計算できて、元の解も求まった。

Depends on

• Polynomial Taylor Shift (Src/FPS/PolynomialTaylorShift.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

// #define PROBLEM "https://atcoder.jp/contests/abc215/tasks/abc215_g"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 215 G - Colorful Candies 2
 * https://atcoder.jp/contests/abc215/submissions/65595540
 */

#include "../../Src/FPS/PolynomialTaylorShift.hpp"

#include "atcoder/modint"
#include "atcoder/convolution"
using mint = atcoder::modint998244353;

#include <iostream>
#include <vector>
#include <algorithm>
int N, C[50050];
int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::cin >> N;
    for (int i = 0 ; i < N ; i++) std::cin >> C[i];
    std::ranges::sort(C, C + N);
    int cnt = 0;
    std::vector<mint> a(N + 1);
    for (int i = 0, j = 0 ; i < N ; i = j) {
        while (j < N and C[i] == C[j]) j++;
        a[N - (j - i)]++;
        cnt++;
    }
    auto b = zawa::PolynomialTaylorShift(a, 1, atcoder::convolution<mint>);
    std::vector<mint> fact(N + 1, 1), invfact(N + 1);
    for (int i = 1 ; i <= N ; i++) fact[i] = fact[i - 1] * mint::raw(i);
    invfact[N] = fact[N].inv();
    for (int i = N ; i >= 1 ; i--) invfact[i - 1] = invfact[i] * mint::raw(i);
    for (int k = 1 ; k <= N ; k++) {
        mint ans = mint{cnt} - b[k] * invfact[N] * fact[k] * fact[N - k];
        std::cout << ans.val() << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/modint: line -1: no such header

Back to top page