結果
問題 |
No.2245 Second Smallest
|
ユーザー |
![]() |
提出日時 | 2023-01-14 01:47:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 1,721 bytes |
コンパイル時間 | 4,479 ms |
コンパイル使用メモリ | 253,692 KB |
最終ジャッジ日時 | 2025-02-10 03:26:58 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using mint = modint998244353; template<typename T> struct Binom{ Binom(int lim = 300000){ extend(lim); } static T fact(int x) { if (x < 0) return T(0); extend(x); return kaijo[x]; } static T ifact(int x){ if (x < 0) return T(0); extend(x); return kainv[x]; } static T C(int n, int r){ if (n < 0 || n < r || r < 0) return T(0); extend(n); return kaijo[n] * kainv[r] * kainv[n-r]; } T operator()(int n, int r){ return C(n,r); } template<class... Cnts> static T M(const Cnts&... cnts){ return multinomial(0,T(1),cnts...); } private: static std::vector<T> kaijo, kainv; static void extend(int lim){ int siz = kaijo.size(); if (siz > lim) return ; int nsiz = siz * 2; kaijo.resize(nsiz+1), kainv.resize(nsiz+1); for (int i = siz; i <= nsiz; i++) kaijo[i] = kaijo[i-1] * T(i); kainv[nsiz] = kaijo[nsiz].inv(); for (int i = nsiz-1; i >= siz; i--) kainv[i] = kainv[i+1] * T(i+1); extend(lim); } }; template<typename T> std::vector<T>Binom<T>::kaijo = vector<T>(2,T(1)); template<typename T> std::vector<T>Binom<T>::kainv = vector<T>(2,T(1)); int main(){ int h, w, k; cin >> h >> w >> k; if (h > w) swap(h,w); Binom<mint> bnm; mint facthw = 1; for (int i = -h+1; i <= k; i++) facthw *= h*w+i; facthw = facthw.inv(); mint ans = 0; for (int c = h; c >= 0; c--){ ans += bnm(h,c) * bnm(w,c) * bnm.fact(c+k-1) * facthw; facthw *= (h*w-c+1); } ans *= k; cout << ans.val() << endl; }