結果
問題 | No.1866 Unfair Tournament |
ユーザー | Cyanmond |
提出日時 | 2022-03-03 23:52:51 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 593 ms / 3,000 ms |
コード長 | 2,320 bytes |
コンパイル時間 | 5,237 ms |
コンパイル使用メモリ | 272,492 KB |
実行使用メモリ | 21,828 KB |
最終ジャッジ日時 | 2023-09-25 21:20:43 |
合計ジャッジ時間 | 10,331 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 20 ms
15,160 KB |
testcase_01 | AC | 20 ms
15,116 KB |
testcase_02 | AC | 21 ms
15,192 KB |
testcase_03 | AC | 20 ms
15,348 KB |
testcase_04 | AC | 20 ms
15,112 KB |
testcase_05 | AC | 20 ms
15,140 KB |
testcase_06 | AC | 21 ms
15,120 KB |
testcase_07 | AC | 24 ms
15,280 KB |
testcase_08 | AC | 20 ms
15,148 KB |
testcase_09 | AC | 29 ms
15,256 KB |
testcase_10 | AC | 22 ms
15,256 KB |
testcase_11 | AC | 21 ms
15,128 KB |
testcase_12 | AC | 589 ms
21,620 KB |
testcase_13 | AC | 590 ms
21,828 KB |
testcase_14 | AC | 589 ms
21,688 KB |
testcase_15 | AC | 590 ms
21,688 KB |
testcase_16 | AC | 589 ms
21,680 KB |
testcase_17 | AC | 593 ms
21,724 KB |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using Fp = modint998244353; #define REP_2(i, n) for (int i = 0; i < (n); ++i) #define REP_3(i, l, r) for (int i = (l); i < (r); ++i) template <int S> struct mint_data { static inline array<Fp, S + 1> fact, inv, inv_fact; static void build() { fact[0] = fact[1] = inv[1] = inv_fact[0] = inv_fact[1] = 1; REP_3(i, 2, S + 1) { fact[i] = fact[i - 1] * i; inv[i] = -(Fp::mod() / i) * inv[Fp::mod() % i]; inv_fact[i] = inv_fact[i - 1] * inv[i]; } } static Fp comb(const int n, const int k) { assert(0 <= k and k <= n and n <= S); return fact[n] * inv_fact[n - k] * inv_fact[k]; } }; using combd = mint_data<1000000>; int read() { int ret; cin >> ret; return ret; } void out(const int n) { cout << n << endl; return; } int main() { const int N = read(); const int A = read(); const int B = read(); const Fp T = Fp(A) / Fp(B); combd::build(); vector<vector<Fp>> f(N); f[0] = {0, 1}; REP_2(d, N - 1) { const int m = 1 << d; assert((int)f[d].size() == m + 1); auto a = f[d]; vector<Fp> rz(m + 1); REP_2(i, m + 1) rz[i] = 1 - a[i]; REP_2(i, m + 1) { a[i] *= combd::comb(m, i); rz[i] *= combd::comb(m, i); } auto cvd1 = convolution<Fp>(a, a); auto cvd2 = convolution<Fp>(a, rz); f[d + 1].resize(2 * m + 1); REP_2(i, 2 * m + 1) { f[d + 1][i] = cvd1[i] + T * (2 * cvd2[i]); f[d + 1][i] /= combd::comb(2 * m, i); } } vector<vector<Fp>> g(N + 1); g[0] = {1}; REP_2(d, N) { const int m = 1 << d; assert((int)g[d].size() == m); auto a = g[d]; vector<Fp> rz(m + 1); REP_2(i, m + 1) rz[i] = (1 - T) * f[d][i] + T * (1 - f[d][i]); REP_2(i, m) a[i] *= combd::comb(m - 1, i); REP_2(i, m + 1) rz[i] *= combd::comb(m, i); auto cvd = convolution<Fp>(a, rz); g[d + 1].resize(2 * m); REP_2(i, 2 * m) { g[d + 1][i] = cvd[i]; g[d + 1][i] /= combd::comb(2 * m - 1, i); } } for (const Fp e : g[N]) out(e.val()); }