結果

問題 No.3119 A Little Cheat
コンテスト
ユーザー ponjuice
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0