結果

問題 No.3119 A Little Cheat
コンテスト
ユーザー hiikunZ
提出日時 2025-04-18 21:47:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 3,518 bytes
コンパイル時間 1,890 ms
コンパイル使用メモリ 198,872 KB
実行使用メモリ 814,524 KB
最終ジャッジ日時 2025-04-18 21:47:16
合計ジャッジ時間 9,658 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Fast exponentiation modulo MOD
ll modpow(ll a, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

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

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

    // Precompute sum_A = sum_{i=1..N} (M - A[i]) mod
    ll sumA = 0;
    for (int i = 0; i < N; i++) {
        sumA = (sumA + (M - A[i])) % MOD;
    }

    // Term1 = M^{N-1} * sumA  (sum of original matches over all B)
    ll term1 = modpow(M, N - 1) * sumA % MOD;

    // If N == 1, no swaps possible => answer = term1
    if (N == 1) {
        cout << term1 << "\n";
        return 0;
    }

    // DP to count D = # of B with no swap giving positive gain
    // dp[v] = number of ways for prefix ending with B_i = v
    vector<ll> dp(M+2, 1), nxt(M+2, 0), pref(M+2, 0), diff(M+3, 0);
    // Initial dp for i=1: all 1
    ll S = M;  // total sum of dp

    for(int i = 0; i < N-1; i++){
        int alpha = A[i], beta = A[i+1];

        // Build prefix sums of dp
        pref[0] = 0;
        for(int v = 1; v <= M; v++){
            pref[v] = (pref[v-1] + dp[v]) % MOD;
        }
        // reset diff array
        fill(diff.begin(), diff.end(), 0LL);

        if (alpha < beta) {
            // T = sum dp[v] for v in (alpha, beta]
            ll T = (pref[beta] - pref[alpha] + MOD) % MOD;
            // From u with h(u)=1: add T to all v
            diff[1] = (diff[1] + T) % MOD;
            diff[M+1] = (diff[M+1] - T + MOD) % MOD;
            // From u with h(u)=0: sum = S-T, add to v in [1..alpha] and [beta+1..M]
            ll U = (S - T + MOD) % MOD;
            // [1..alpha]
            diff[1] = (diff[1] + U) % MOD;
            diff[alpha+1] = (diff[alpha+1] - U + MOD) % MOD;
            // [beta+1..M]
            diff[beta+1] = (diff[beta+1] + U) % MOD;
            diff[M+1] = (diff[M+1] - U + MOD) % MOD;
        }
        else if (alpha > beta) {
            // Usum = sum dp[v] for v in [1..beta] and [alpha+1..M]
            ll U1 = pref[beta];
            ll U2 = (S - pref[alpha] + MOD) % MOD;
            ll U = (U1 + U2) % MOD;
            // From u in U-group: add U to all v
            diff[1] = (diff[1] + U) % MOD;
            diff[M+1] = (diff[M+1] - U + MOD) % MOD;
            // From u in mid ((beta..alpha]): sum = S-U, add to v in [beta+1..alpha]
            ll mid = (S - U + MOD) % MOD;
            diff[beta+1] = (diff[beta+1] + mid) % MOD;
            diff[alpha+1] = (diff[alpha+1] - mid + MOD) % MOD;
        }
        else {
            // alpha == beta: all transitions allowed, dp[i+1][*] = S
            diff[1] = (diff[1] + S) % MOD;
            diff[M+1] = (diff[M+1] - S + MOD) % MOD;
        }

        // Build nxt from diff by prefix sums
        ll acc = 0;
        for(int v = 1; v <= M; v++){
            acc = (acc + diff[v]) % MOD;
            nxt[v] = acc;
        }
        // swap dp and nxt, update S
        S = 0;
        for(int v = 1; v <= M; v++){
            dp[v] = nxt[v];
            S = (S + dp[v]) % MOD;
        }
    }

    ll D = S;  // number of B with no positive swap gain
    // Total B = M^N; C1 = total - D
    ll total = modpow(M, N);
    ll C1 = (total - D + MOD) % MOD;

    ll answer = (term1 + C1) % MOD;
    cout << answer << "\n";
    return 0;
}
0