結果

問題 No.3004 ヤング図形
ユーザー lif4635
提出日時 2025-01-17 22:13:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,632 bytes
コンパイル時間 909 ms
コンパイル使用メモリ 103,736 KB
実行使用メモリ 817,792 KB
最終ジャッジ日時 2025-01-17 22:13:30
合計ジャッジ時間 17,803 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 MLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 998244353;

// Combクラス：階乗と逆元を計算するクラス
class Comb {
public:
    vector<long long> fac, finv;
    int mod;

    // コンストラクタで階乗と逆元を事前に計算
    Comb(int lim, int mod = MOD) : mod(mod) {
        fac.resize(lim + 1, 1);
        finv.resize(lim + 1, 1);
        for (int i = 2; i <= lim; ++i) {
            fac[i] = fac[i - 1] * i % mod;
        }
        finv[lim] = modInverse(fac[lim], mod);
        for (int i = lim - 1; i >= 1; --i) {
            finv[i] = finv[i + 1] * (i + 1) % mod;
        }
    }

    // 組み合わせ C(a, b)
    long long C(int a, int b) {
        if (b < 0 || a < b) return 0;
        return fac[a] * finv[b] % mod * finv[a - b] % mod;
    }

    // 順列 P(a, b)
    long long P(int a, int b) {
        if (b < 0 || a < b) return 0;
        return fac[a] * finv[a - b] % mod;
    }

    // 重複組み合わせ H(a, b)
    long long H(int a, int b) {
        return C(a + b - 1, b);
    }

    // 階乗
    long long F(int a) {
        return fac[a];
    }

    // 階乗の逆元
    long long Fi(int a) {
        return finv[a];
    }

private:
    // モジュラ逆元を求める
    long long modInverse(long long a, int m) {
        long long m0 = m, t, q;
        long long x0 = 0, x1 = 1;
        if (m == 1) return 0;
        while (a > 1) {
            q = a / m;
            t = m;
            m = a % m;
            a = t;
            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }
        if (x1 < 0) x1 += m0;
        return x1;
    }
};

int main() {
    int k;
    cin >> k;

    vector<int> ls(k), rs(k);
    long long sm = 0;
    long long ans = 1;

    // 入力を受け取る
    for (int i = 0; i < k; ++i) {
        cin >> ls[i] >> rs[i];
        sm += (long long)ls[i] * rs[i];
    }

    // 最大値を使ってCombオブジェクトを初期化
    Comb comb(max(*max_element(ls.begin(), ls.end()), *max_element(rs.begin(), rs.end())));

    // 計算を行う
    for (int i = 0; i < k; ++i) {
        int l = ls[i], m = rs[i];

        // comb.Fi(l) を m 回掛け算する
        long long tmp = 1;
        for (int j = 0; j < m; ++j) {
            tmp = tmp * comb.Fi(l) % MOD;
        }
        ans = ans * tmp % MOD;

        // comb.Fi(m) を掛け算する
        ans = ans * comb.Fi(m) % MOD;
        ans %= MOD;
    }

    // 階乗計算
    for (int i = 1; i <= sm; ++i) {
        ans = ans * i % MOD;
    }

    // 結果を出力
    cout << ans << endl;

    return 0;
}
0