結果
問題 | 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 |
ソースコード
#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;}