結果

問題 No.3004 ヤング図形
ユーザー Mao-beta
提出日時 2025-02-03 14:13:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,785 bytes
コンパイル時間 5,340 ms
コンパイル使用メモリ 198,596 KB
実行使用メモリ 816,640 KB
最終ジャッジ日時 2025-02-03 14:13:38
合計ジャッジ時間 34,978 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 MLE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
 
// The modulus used in calculations.
const ll MOD = 998244353;
 
// Returns a % mod in the range [0, mod-1]
inline ll safe_mod(ll a, ll mod = MOD) {
    ll res = a % mod;
    if (res < 0)
        res += mod;
    return res;
}
 
// Safe multiplication modulo mod using __int128 to avoid overflow.
// This function first reduces both factors to the range [0, mod-1].
inline ll mulmod(ll a, ll b, ll mod = MOD) {
    a = safe_mod(a, mod);
    b = safe_mod(b, mod);
    return ( (__int128) a * b ) % mod;
}
 
// Fast modular exponentiation with safe modulo operations.
ll modPow(ll base, ll exp, ll mod = MOD) {
    ll result = 1;
    base = safe_mod(base, mod);
    while(exp > 0) {
        if(exp & 1)
            result = mulmod(result, base, mod);
        base = mulmod(base, base, mod);
        exp >>= 1;
    }
    return result;
}
 
// Combination class: precomputes factorials and inverses modulo mod.
struct Comb {
    int n;
    ll mod;
    vector<ll> fac, inv;
    
    // Constructor precomputes factorials and inverses up to n.
    Comb(int n, ll mod) : n(n), mod(mod) {
        fac.resize(n + 1);
        inv.resize(n + 1);
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = mulmod(fac[i - 1], i, mod);
        }
        // Compute the modular inverse of fac[n] using Fermat's little theorem.
        inv[n] = modPow(fac[n], mod - 2, mod);
        for (int i = n - 1; i >= 0; i--) {
            inv[i] = mulmod(inv[i + 1], i + 1, mod);
        }
    }
    
    // Returns C(n, r) modulo mod.
    ll C(int n, int r) {
        if(r < 0 || r > n) return 0;
        return mulmod(mulmod(fac[n], inv[r], mod), inv[n - r], mod);
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int K;
    cin >> K;
    vector<pair<int, int>> LM(K);
    ll total = 0;
    for (int i = 0; i < K; i++){
        int l, m;
        cin >> l >> m;
        LM[i] = {l, m};
        total += (ll)l * m;
    }
    
    int N = (int) total;
    // Initialize the combination object with N+1.
    Comb comb(N + 1, MOD);
    
    ll ans = 1;
    // Process the groups in reverse order (mirroring Python's LM[::-1]).
    for (int i = K - 1; i >= 0; i--){
        int l = LM[i].first;
        int m = LM[i].second;
        int lm = l * m;  // Total items in this group.
        // tmp starts as C(N, l*m)
        ll tmp = comb.C(N, lm);
        // For each occurrence in this group, multiply by C(lm-1, l-1)
        for (int j = 0; j < m; j++){
            tmp = mulmod(tmp, comb.C(lm - 1, l - 1), MOD);
            lm -= l;
            N -= l;
        }
        ans = mulmod(ans, tmp, MOD);
    }
    
    // Print the final answer.
    cout << ans << "\n";
    return 0;
}
0