結果
問題 | No.2529 Treasure Hunter |
ユーザー |
![]() |
提出日時 | 2023-11-03 22:59:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 614 bytes |
コンパイル時間 | 4,241 ms |
コンパイル使用メモリ | 255,268 KB |
最終ジャッジ日時 | 2025-02-17 18:46:03 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using mint = atcoder::modint998244353;void solve() {long long N, M;cin >> M >> N;vector<vector<mint>> dp(N+1, vector<mint>(3));dp[0][0] = 1;for( int i = 1; i <= N; i++ ) {dp[i][0] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2];dp[i][1] = dp[i-1][0]*M+dp[i-1][1]*(M-1)+dp[i-1][2]*(M-2);dp[i][2] = dp[i-1][0]*max(0LL, M*(M-3)/2)+dp[i-1][1]*max(0LL, (M-2)*(M-3)/2)+dp[i-1][2]*max(0LL, (M*M-7*M+14)/2);}cout << accumulate(dp[N].begin(), dp[N].end(), mint(0)).val() << endl;}int main() {int T;cin >> T;while(T--) { solve(); }}