結果
問題 | No.2303 Frog on Grid |
ユーザー |
![]() |
提出日時 | 2024-11-08 01:20:34 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 845 bytes |
コンパイル時間 | 3,613 ms |
コンパイル使用メモリ | 242,476 KB |
実行使用メモリ | 12,876 KB |
最終ジャッジ日時 | 2024-11-08 01:20:39 |
合計ジャッジ時間 | 5,152 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std;void fast_io() {ios_base::sync_with_stdio(false);cin.tie(nullptr);}#include <atcoder/convolution>#include <atcoder/modint>using namespace atcoder;using mint = modint998244353;int main() {fast_io();int h, w;cin >> h >> w;int N = h + w;vector<mint> fact(N + 1), inv(N + 1);fact[0] = 1;for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i;inv[N] = fact[N].inv();for (int i = N; i >= 1; i--) inv[i - 1] = inv[i] * i;vector<mint> f(h + 1), g(w + 1);for (int i = 0; i <= h / 2; i++) {int j = h - 2 * i;f[i + j] = inv[i] * inv[j];}for (int i = 0; i <= w / 2; i++) {int j = w - 2 * i;g[i + j] = inv[i] * inv[j];}auto fg = convolution(f, g);mint ans = 0;for (int i = 0; i <= h + w; i++) {ans += fg[i] * fact[i];}cout << ans.val() << endl;}