結果
問題 |
No.3175 転移迷宮 (Easy)
|
ユーザー |
![]() |
提出日時 | 2025-06-07 09:38:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 3,000 ms |
コード長 | 1,499 bytes |
コンパイル時間 | 1,917 ms |
コンパイル使用メモリ | 200,256 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-06-07 09:38:15 |
合計ジャッジ時間 | 4,596 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 44 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint.hpp> using namespace std; using i32 = int; using i64 = long long; using f64 = long double; using i128 = __int128_t; using p2 = pair<i64, i64>; using el = tuple<i64, i64, i64>; using mint = atcoder::modint998244353; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } i64 pow(i64 x, i64 n) { i64 res = 1; i64 t = x; while (n > 0) { if (n & 1) { res = res * t; } t = t * t; } return res; } void _main() { i64 ttt; cin >> ttt; for (;ttt--;) { i64 n, k; cin >> n >> k; vector<vector<mint>> dp(n, vector<mint>(n + 1, 0)); for (i64 i = 0; i < n; i++) { dp[i][i] = 1; } mint rev = mint(1) / (2 * k + 1); for (i64 i = 0; i < n; i++) { dp[i][i] = 0, dp[i][n] = 1; for (i64 j = -k; j <= k; j++) { i64 ni = i + j; if (ni < 0 || ni >= n) continue; if (ni == i) { dp[i][i] += rev; continue; } for (i64 l = i; l <= n; l++) { dp[i][l] += dp[ni][l] * rev; } } mint p = mint(1) / (mint(1) - dp[i][i]); dp[i][i] = 0; for (i64 j = 0; j <= n; j++) { dp[i][j] *= p; } for (i64 j = 0; j < i; j++) { for (i64 l = i + 1; l <= n; l++) { dp[j][l] += dp[j][i] * dp[i][l]; } dp[j][i] = 0; } } for (i64 i = 0; i < n; i++) { cout << dp[i][n].val() << " "; } cout << "\n"; } }