結果

問題 No.3119 A Little Cheat
ユーザー hiikunZ
提出日時 2025-04-18 22:17:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 104 ms / 2,000 ms
コード長 1,592 bytes
コンパイル時間 2,026 ms
コンパイル使用メモリ 203,404 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2025-04-18 22:17:11
合計ジャッジ時間 7,389 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

ll modpow(ll A,ll B,ll M){
    ll r = 1,p = A;
    while(B > 0){
        if(B % 2 == 1) r = (r * p) % M;
        p = (p * p) % M;
        B /= 2;
    }
    return r;
}


int main() {
    ll N,M;
    cin >> N >> M;
    vector<ll> A(N + 100);
    for(ll i = 0; i < N; i++) {
        cin >> A[i + 1];
    }
    ll ans = 0;
    {
        ll s = 0;
        for(ll i = 1;i <= N;i++){
            s += M - A[i];
            s %= MOD;
        }
        ans += (modpow(M,N - 1,MOD) * s) % MOD;
        ans %= MOD;
    }
    ans += modpow(M,N,MOD);
    //cerr << "ans = " << ans << endl;

    vector<vector<ll>> DP(3,vector<ll>(N + 10,0));
    DP[2][1] = 1;
    for(ll i = 1;i <= N;i++){
        vector<ll> kugiri = {0,A[i - 1],A[i],A[i + 1],M};
        sort(kugiri.begin(),kugiri.end());
        kugiri.erase(unique(kugiri.begin(),kugiri.end()),kugiri.end());
        for(ll x = 0;x < (ll)kugiri.size()-1;x++){
            ll st = kugiri[x] + 1,en = kugiri[x + 1];
            ll p = (st > A[i - 1]) - (st > A[i]) + 1;
            ll q = (st > A[i]) - (st > A[i + 1]) + 1;
            //cerr << st << " " << en << " " << p << " " << q << endl;
            for(ll s = 0;s < 3;s++){
                if(s >= p){
                    DP[q][i + 1] += DP[s][i] * (en - st + 1) % MOD;
                    DP[q][i + 1] %= MOD;
                }
            }
        }
    }
    for(ll i = 0;i < 3;i++){
        ans -= DP[i][N + 1];
        ans %= MOD;
    }
    if(ans < 0) ans += MOD;
    cout << ans << endl;
}
0