結果

問題 No.1866 Unfair Tournament
コンテスト
ユーザー dekomori_sanae
提出日時 2022-03-25 20:10:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,606 ms / 3,000 ms
コード長 3,552 bytes
コンパイル時間 4,589 ms
コンパイル使用メモリ 142,420 KB
実行使用メモリ 177,420 KB
最終ジャッジ日時 2024-10-14 04:10:12
合計ジャッジ時間 14,699 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
#include <atcoder/convolution>
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 998244353;
const ll INF = 1e16;

const ll MAX = 300000;

ll fact[MAX];  // fact[i] : iの階乗のmod
ll inv[MAX];  // inv[i] : iの逆数のmod
ll invfact[MAX];  // invfact[i] : iの階乗の逆数のmod

void init() {
    fact[0] = 1;
    inv[0] = inv[1] = 1;
    invfact[0] = 1;
    for(ll i = 1; i < MAX; i++) {
        fact[i] = i * fact[i-1] % mod;
        if(i >= 2) {
            inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        }
        invfact[i] = invfact[i-1] * inv[i] % mod;
    }
}

// nCrをO(n)で求める。 
ll Comb(ll n, ll r) {
    if(r < 0 || n < 0 || n < r) {
        return 0;
    }
    ll res = fact[n];
    res = (res * invfact[r]) % mod;
    res = (res * invfact[n - r]) % mod;
    return res;
}

// a^n (mod.MOD)を求める。計算量はO(logn)
ll modpow(ll a, ll n, ll MOD = mod) {
    if(n == 0) {
        return 1;
    }
    if(n % 2 == 1) {
        return a * modpow(a, n-1, MOD) % MOD;
    }
    return modpow(a, n/2, MOD) * modpow(a, n/2, MOD) % MOD;
}
 
int main() {
    ll n, A, B;
    cin >> n >> A >> B;

    init();

    ll p = A * modpow(B, mod - 2) % mod;

    vl two(n+1);  // two[i] : 2^i
    two[0] = 1;
    exrep(i, 1, n) {
        two[i] = 2 * two[i-1];
    }

    vvl vec1(n, vl(two[n] + 1));  // vec1[i][m] : 1 / Comb(2^(i+1), m)
    vvl vec2(n, vl(two[n] + 1));  // vec2[i][m] : 1 / Comb(2^(i+1) - 1, m)
    rep(i, n) {
        exrep(m, 0, two[i+1]) {
            vec1[i][m] = modpow(Comb(two[i+1], m), mod - 2);
            vec2[i][m] = modpow(Comb(two[i+1] - 1, m), mod - 2);
        }
    }

    vvl g(n+1, vl(two[n] + 1));  // g[i][j] : サイズiのトーナメントに1が含まれず、0がj個のとき0が勝つ確率
    g[0][1] = 1;
    rep(i, n) {
        vl c(two[i+1] + 1);
        vl d(two[i+1] + 1);
        exrep(j, 0, two[i+1]) {
            c[j] = Comb(two[i], j) * g[i][j] % mod;
            d[j] = Comb(two[i], j);
        }
        vl v1 = convolution<mod>(c, c);
        vl v2 = convolution<mod>(c, d);
        exrep(m, 0, two[i+1]) {
            g[i+1][m] = ((1 + 2*mod - 2*p) * v1[m] + 2 * p * v2[m]) % mod * vec1[i][m] % mod;
        }
    }

    vvl f(n+1, vl(two[n]));  // f[i][j] : サイズiのトーナメントに1が含まれて、0がj個のとき1が勝つ確率
    f[0][0] = 1;
    rep(i, n) {
        vl a(two[i+1]);
        vl b(two[i+1]);
        rep(j, two[i+1]) {
            a[j] = Comb(two[i] - 1, j) * f[i][j] % mod;
            b[j] = Comb(two[i], j) * ((1 + 2*mod - 2*p) * g[i][j] % mod + p) % mod;
        }
        vl v = convolution<mod>(a, b);
        rep(m, two[i+1]) {
            f[i+1][m] = v[m] * vec2[i][m] % mod;
        }
    }

    rep(x, two[n]) {
        cout << f[n][x] << "\n";
    }

    re0;
}
0