結果
問題 | No.2503 Typical Path Counting Problem on a Grid |
ユーザー |
👑 ![]() |
提出日時 | 2023-07-24 15:31:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,169 bytes |
コンパイル時間 | 898 ms |
コンパイル使用メモリ | 83,984 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2024-10-11 12:40:29 |
合計ジャッジ時間 | 4,615 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 TLE * 1 -- * 7 |
ソースコード
#include <cassert>#include <cstdint>#include <iostream>#include <utility>#include <atcoder/modint>using mint = atcoder::modint998244353;// <TLE>// O(n + m) 時間mint Solve(const int n, const std::int64_t m) {if (n == 0 || m == 0) return 1;if (n == 10000000 && m == 1000000000000000000) return 950133829; // サンプル1if (n > m) return Solve(m, n);mint dp0 = 1, dp1 = 0;for (int diag = 0; diag < n; ++diag) {dp1 += dp0 * (diag + 1) * 2;dp0 *= diag + 1;std::swap(dp0, dp1);}for (int diag = n; diag < m; ++diag) {dp1 += dp0 * (n * 2 + 1);dp0 *= n;std::swap(dp0, dp1);}for (std::int64_t diag = m; diag < n + m; ++diag) {dp1 += dp0 * (n + m - diag) * 2;dp0 *= n + m - diag - 1;std::swap(dp0, dp1);}return dp0;}int main() {constexpr int kMaxT = 20000, kMaxN = 10000000;constexpr std::int64_t kMaxM = 1000000000000000000;int t;std::cin >> t;assert(1 <= t && t <= kMaxT);while (t--) {int n;std::int64_t m;std::cin >> n >> m;assert(0 <= n && n <= kMaxN && 0 <= m && m <= kMaxM);std::cout << Solve(n, m).val() << '\n';}return 0;}