結果

問題 No.2303 Frog on Grid
ユーザー eve__fuyuki
提出日時 2024-11-08 01:20:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 48 ms / 2,000 ms
コード長 845 bytes
コンパイル時間 3,518 ms
コンパイル使用メモリ 232,068 KB
最終ジャッジ日時 2025-02-25 02:33:05
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0