結果

問題 No.3160 Party Game
コンテスト
ユーザー Salt
提出日時 2026-03-06 21:29:53
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 2,113 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,234 ms
コンパイル使用メモリ 340,004 KB
実行使用メモリ 34,584 KB
最終ジャッジ日時 2026-03-06 21:32:24
合計ジャッジ時間 5,772 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif

#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//https://boostjp.github.io/tips/multiprec-int.html

#define YES cout<<"Yes\n"
#define NO cout<<"No\n"
#define YN {cout<<"Yes\n";}else{cout<<"No\n";}// if(a==b)YN;
#define NO2 cout<<"-1\n"

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i=int(n)-1; i>=0; --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

ll MOD = 998244353;
ll modpow(ll n, int p) {
    // n^p
    ll base = n, ans = 1;
    while(p>0) {
        if (p%2) {
            ans *= base; ans%=MOD;
        }
        base *= base; base %= MOD;
        p /= 2;
    }
    return ans;
}

ll moddiv(ll n) {
    // n^(-1)
    return modpow(n, MOD-2);
}

vector<ll> fact, fact_inv;
void build() {
    int n = fact.size();
    fact[0] = 1;
    rep(i,n-1) {
        fact[i+1] = fact[i] * (i+1) % MOD;
    }
    fact_inv[n-1] = moddiv(fact[n-1]);
    rrep(i,n-1) {
        fact_inv[i] = fact_inv[i+1] * (i+1) % MOD;
    }
    return;
}

ll comb(ll n, ll r) {
    // nCr
    r = min(r, n-r);
    if (r==0) return 1;
    return fact[n] * fact_inv[r] % MOD * fact_inv[n-r] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N,M;
    cin>>N>>M;
    fact.resize(N+M+1);
    fact_inv.resize(N+M+1);
    build();
    
    vector<ll> tmp;
    for (int i=0; M-N*i>=0; ++i) {
        // N人に先にi個配った後、N人で(0~M-Ni)個を分配する方法
        // N人に先にi個配った後、N+1人でM-Ni個を分配する方法
        // サイコロの目のmaxはM-1であることに注意
        ll cur = comb(M+N-N*i, N);
        if (N == 1 || i == 0) {
            cur -= N;
            while (cur<0) cur += MOD;
        }
        tmp.emplace_back(cur);
    }
    tmp.emplace_back(0);

    ll ans = 0;
    for (int i=0; M-N*i>=0; ++i) {
        ll t = tmp[i] - tmp[i+1];
        while(t<0) t += MOD; t %= MOD;
        ans += i*t; ans %= MOD;
    }

    ans *= moddiv(tmp[0]); ans %= MOD;
    cout << ans << endl;
}
0