結果
問題 | No.2529 Treasure Hunter |
ユーザー |
|
提出日時 | 2023-11-03 22:36:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 1,092 bytes |
コンパイル時間 | 647 ms |
コンパイル使用メモリ | 67,044 KB |
最終ジャッジ日時 | 2025-02-17 18:36:34 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
// #include <bits/stdc++.h>#include <iostream>using namespace std;using ll = long long;ll const m = 998244353;void solve() {int N, M;cin >> N >> M;if (N < 4) {ll ans[] = {1ll, (ll)N};while (--M) {// cout << (ans[0] + ans[1]) % m << endl;ll a2[2];a2[0] = ans[0] + ans[1];a2[1] = ans[0] * N + ans[1] * (N - 1);ans[0] = a2[0] % m; ans[1] = a2[1] % m;}cout << (ans[0] + ans[1]) % m << endl;} else {// swap(N, M);ll ans[3];ans[0] = 1;ans[1] = N;ans[2] = N;ans[2] *= (N - 3);ans[2] /= 2;ans[2] %= m;ll X[3];X[0] = ans[2];X[1] = N - 2;X[1] = (X[1] * (N - 3)) / 2;X[2] = N - 2;X[2] = (X[2] * (N - 3)) / 2 - (N - 4);X[1] %= m; X[2] %= m;while (--M) {ll a2[3];a2[0] = ans[0] + ans[1] + ans[2];a2[1] = ans[0] * N + ans[1] * (N - 1) + ans[2] * (N - 2);a2[2] = ans[0] * X[0] + ans[1] * X[1] + ans[2] * X[2];for (int i = 0; i < 3; i ++) ans[i] = a2[i] % m;}cout << (ans[0] + ans[1] + ans[2]) % m << endl;}}int main () {int T;cin >> T;while (T--) {solve();}}