結果
問題 | No.2303 Frog on Grid |
ユーザー | t98slider |
提出日時 | 2023-05-13 15:57:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 781 bytes |
コンパイル時間 | 4,252 ms |
コンパイル使用メモリ | 237,812 KB |
実行使用メモリ | 12,748 KB |
最終ジャッジ日時 | 2024-11-29 08:16:49 |
合計ジャッジ時間 | 5,224 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; int main(){ ios::sync_with_stdio(false); cin.tie(0); int H, W; cin >> H >> W; vector<mint> fact(H + W + 1), inv(H + W + 1), a(H + 1), b(W + 1); fact[0] = 1; for(int i = 1; i <= H + W; i++) fact[i] = i * fact[i - 1]; inv[H + W] = 1 / fact[H + W]; for(int i = H + W; i >= 1; i--) inv[i - 1] = i * inv[i]; for(int i = 0; i <= H / 2; i++) a[H - i] = inv[i] * inv[H - 2 * i]; for(int i = 0; i <= W / 2; i++) b[W - i] = inv[i] * inv[W - 2 * i]; auto c = convolution(a, b); mint ans; for(int i = (H + W) / 2; i <= H + W; i++) ans += fact[i] * c[i]; cout << ans.val() << '\n'; }