結果

問題 No.3119 A Little Cheat
コンテスト
ユーザー keigo kuwata
提出日時 2025-04-24 15:09:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 3,841 bytes
コンパイル時間 2,549 ms
コンパイル使用メモリ 206,892 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-24 15:09:27
合計ジャッジ時間 6,342 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 MOD = 998244353;

// a, b の関係から d(v) in {-1,0,1} の区間長を返す
// 返り値は { {d, count}, ... }
vector<pair<int, int64>> segments_pair(int64 a, int64 b, int64 M) {
    int64 diff = llabs(b - a);
    if (diff == 0) {
        // 全域で d = 0
        return {{0, M}};
    }
    int dval = (b > a ? 1 : -1);
    // (min(a,b), max(a,b)] では d = dval, それ以外では 0
    return {
        {dval, diff},
        {0, M - diff}
    };
}

// x^e mod MOD
int64 modpow(int64 x, int64 e) {
    int64 r = 1;
    x %= MOD;
    while (e) {
        if (e & 1) r = (r * x) % MOD;
        x = (x * x) % MOD;
        e >>= 1;
    }
    return r;
}

// d in {-1,0,1} を配列 index 0..2 にマップ
inline int d2i(int d) { return d + 1; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    int64 M;
    cin >> N >> M;
    vector<int64> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // 1) S0 = M^{N-1} * sum_i (M - A[i]) % MOD
    int64 Mmod = M % MOD;
    int64 pow_M_N1 = modpow(Mmod, N - 1);
    int64 sum_diff = 0;
    for (int i = 0; i < N; i++) {
        sum_diff = (sum_diff + (M - A[i]) % MOD) % MOD;
    }
    int64 S0 = (pow_M_N1 * sum_diff) % MOD;

    // 2) 全列数 T = M^N % MOD
    int64 T = modpow(Mmod, N);

    // 3) DP で T0（交換してもスコア増加しない全列数）を数える
    // dp_prev[k] = 前のペアで d = k-1（k=0..2）の列数累積
    vector<int64> dp_prev(3, 0), dp_curr(3, 0);

    // 初期化：ペア (A[0], A[1]) について
    for (auto &seg : segments_pair(A[0], A[1], M)) {
        int d = seg.first;
        int64 cnt = seg.second % MOD;
        dp_prev[d2i(d)] = (dp_prev[d2i(d)] + cnt) % MOD;
    }

    // i = 1 .. N-2 の遷移
    for (int i = 1; i <= N - 2; i++) {
        // 区間分割のための境界点集合
        int64 ap = A[i-1], a = A[i], an = A[i+1];
        vector<int64> P = {0, M, ap, a, an};
        sort(P.begin(), P.end());
        P.erase(unique(P.begin(), P.end()), P.end());

        // dp_prev の suffix sum をつくる
        vector<int64> suff(4, 0);
        suff[3] = 0;
        for (int k = 2; k >= 0; k--) {
            suff[k] = (dp_prev[k] + suff[k+1]) % MOD;
        }

        // dp_curr を 0 にリセット
        fill(dp_curr.begin(), dp_curr.end(), 0LL);

        // 各区間 [l..r] について遷移
        for (int j = 0; j + 1 < (int)P.size(); j++) {
            int64 l = P[j] + 1;
            int64 r = P[j+1];
            if (l > r) continue;
            int64 len = (r - l + 1) % MOD;

            // prev_d = d_{i-1}(v)
            int prev_d;
            if (l > min(ap, a) && r <= max(ap, a)) {
                prev_d = (a > ap ? 1 : -1);
            } else {
                prev_d = 0;
            }

            // next_d = d_i(v)
            int next_d;
            if (l > min(a, an) && r <= max(a, an)) {
                next_d = (an > a ? 1 : -1);
            } else {
                next_d = 0;
            }

            // prev_d 以上の d から遷移可能
            int idx_next = d2i(next_d);
            int idx_prev = d2i(prev_d);
            dp_curr[idx_next] = (dp_curr[idx_next] + len * suff[idx_prev]) % MOD;
        }

        dp_prev.swap(dp_curr);
    }

    // 最後のペア (A[N-2], A[N-1]) で T0 を計算
    vector<int64> suff(4, 0);
    for (int k = 2; k >= 0; k--) {
        suff[k] = (dp_prev[k] + suff[k+1]) % MOD;
    }
    int64 T0 = 0;
    for (auto &seg : segments_pair(A[N-2], A[N-1], M)) {
        int d = seg.first;
        int64 cnt = seg.second % MOD;
        T0 = (T0 + cnt * suff[d2i(d)]) % MOD;
    }

    // 最終答え
    int64 ans = (S0 + (T - T0 + MOD)) % MOD;
    cout << ans << "\n";
    return 0;
}
0