結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
|
提出日時 | 2025-04-17 00:17:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 101 ms / 2,000 ms |
コード長 | 3,540 bytes |
コンパイル時間 | 3,386 ms |
コンパイル使用メモリ | 280,480 KB |
実行使用メモリ | 9,092 KB |
最終ジャッジ日時 | 2025-04-17 01:12:36 |
合計ジャッジ時間 | 8,489 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, a, b) for (int i = a; i < (b); i++) const ll mod = 998244353; int main() { int n, m; cin >> n >> m; vector<ll> a(n); rep(i, 0, n) cin >> a[i]; vector<ll> powM(n + 1); powM[0] = 1; rep(i, 0, n) powM[i + 1] = powM[i] * m % mod; // 操作なしで得ることのできる値 ll ans = 0; rep(i, 0, n) { ans += (m - a[i]) * powM[n - 1] % mod; } ans %= mod; // 交換することによって +1 できないパターンが何個あるかを数える // dp[0] := i番目の値がmin(a[i], a[i+1])以下である。 // dp[1] := i番目の値がmin(a[i], a[i+1])より大きいが、max(a[i], a[i+1])以下である。 // dp[2] := i番目の値がmax(a[i], a[i+1])より大きい。 vector<ll> dp(3, 0); dp[0] = min(a[0], a[1]); dp[1] = max(a[0], a[1]) - min(a[0], a[1]); dp[2] = m - max(a[0], a[1]); a.push_back(m); // 何でも良い rep(i, 1, n) { vector<ll> ndp(3, 0); if (a[i-1] < a[i]) { // dp[1] は 交換する価値はない ndp[0] = dp[1] * min(a[i], a[i+1]) % mod; // 交換しない ndp[1] = dp[1] * (max(a[i], a[i+1]) - min(a[i], a[i+1])) % mod; ndp[2] = dp[1] * (m - max(a[i], a[i+1])) % mod; // dp[0],dp[2] は a[i-1] < x <= a[i] を選択する時交換する価値がある // a[i-1] 以下への遷移 if(a[i-1] < a[i+1]) { ndp[0] += (dp[0] + dp[2]) * a[i-1] % mod; } else { ndp[0] += (dp[0] + dp[2]) * a[i+1] % mod; ndp[1] += (dp[0] + dp[2]) * (a[i-1] - a[i+1]) % mod; } // a[i] より大きいものへの遷移 if(a[i] > a[i+1]) { ndp[2] += (dp[0] + dp[2]) * (m - a[i]) % mod; } else { ndp[2] += (dp[0] + dp[2]) * (m - a[i+1]) % mod; ndp[1] += (dp[0] + dp[2]) * (a[i+1] - a[i]) % mod; } } if(a[i-1] == a[i]) { // 交換する必要はない ll res = (dp[0] + dp[1] + dp[2]) % mod; ndp[0] = res * min(a[i], a[i+1]) % mod; ndp[1] = res * (max(a[i], a[i+1]) - min(a[i], a[i+1])) % mod; ndp[2] = res * (m - max(a[i], a[i+1])) % mod; } if(a[i-1] > a[i]) { // dp[0], dp[2] は交換する価値がない ndp[0] = (dp[0] + dp[2]) * min(a[i], a[i+1]) % mod; ndp[1] = (dp[0] + dp[2]) * (max(a[i], a[i+1]) - min(a[i], a[i+1])) % mod; ndp[2] = (dp[0] + dp[2]) * (m - max(a[i], a[i+1])) % mod; // dp[1] は a[i-1] < x または x <= a[i] を選択する時交換する価値がある // a[i] より大きく、 a[i-1] 以下への遷移 if(a[i] > a[i+1]) { ndp[2] += dp[1] * (a[i-1] - a[i]) % mod; } else { if(a[i-1] < a[i+1]) { ndp[1] += dp[1] * (a[i-1] - a[i]) % mod; } else { ndp[2] += dp[1] * (a[i-1] - a[i+1]) % mod; ndp[1] += dp[1] * (a[i+1] - a[i]) % mod; } } } ndp[0] %= mod; ndp[1] %= mod; ndp[2] %= mod; dp.swap(ndp); } ll res = (dp[0] + dp[1] + dp[2]) % mod; ans += (powM[n] - res + mod) % mod; // 出力 cout << ans % mod << endl; }