結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }