結果
問題 | No.2303 Frog on Grid |
ユーザー |
|
提出日時 | 2023-05-12 22:19:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 100 ms / 2,000 ms |
コード長 | 2,003 bytes |
コンパイル時間 | 1,966 ms |
コンパイル使用メモリ | 114,024 KB |
最終ジャッジ日時 | 2025-02-12 23:08:22 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <iostream> #include <atcoder/convolution> using namespace std; #include <cassert> #include <vector> template <typename MODINT> struct CombinationStructure { public: CombinationStructure() { fact = {1, 1}; fact_inverse = {1, 1}; } void size_up(int n) { int old_n = fact.size() - 1; if (n <= old_n) { return; } n = std::max(n, old_n * 2); fact.resize(n + 1); fact_inverse.resize(n + 1); for (int i = old_n + 1; i <= n; i++) { fact[i] = fact[i - 1] * i; } fact_inverse[n] = fact[n].inv(); for (int i = n - 1; i >= old_n + 1; i--) { fact_inverse[i] = fact_inverse[i + 1] * (i + 1); } } MODINT C(int n, int k) { size_up(n); if (k > n || k < 0) { return 0; } return fact[n] * fact_inverse[k] * fact_inverse[n - k]; } MODINT P(int n, int k) { assert(k >= 0); size_up(n); if (k > n) { return 0; } return fact[n] * fact_inverse[n - k]; } MODINT factorial(int n) { size_up(n); return fact[n]; } MODINT operator()(int n, int k) { return C(n, k); } private: int maxn; std::vector<MODINT> fact; std::vector<MODINT> fact_inverse; }; using mint = atcoder::modint998244353; int main() { int h, w; cin >> h >> w; CombinationStructure<mint> com; vector<mint> d(h + 1), e(w + 1); for (int i = 0; i <= h; i++) { int c = i * 2 - h; d[i] = com(i, c) / com.factorial(i); } for (int i = 0; i <= w; i++) { int c = i * 2 - w; e[i] = com(i, c) / com.factorial(i); } vector<mint> r = atcoder::convolution(d, e); mint ans = 0; for (int i = 0; i <= h + w; i++) { ans += r[i] * com.factorial(i); } cout << ans.val() << endl; }