結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
|
提出日時 | 2025-04-20 13:19:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 2,539 bytes |
コンパイル時間 | 2,404 ms |
コンパイル使用メモリ | 199,272 KB |
実行使用メモリ | 10,240 KB |
最終ジャッジ日時 | 2025-04-20 13:19:07 |
合計ジャッジ時間 | 6,308 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; /* a^e (mod MOD) */ long long mod_pow(long long a,long long e){ long long r=1%MOD, x=a%MOD; for(;e;e>>=1,x=(__int128)x*x%MOD) if(e&1) r=(__int128)r*x%MOD; return r; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; long long M; if(!(cin>>N>>M)) return 0; vector<long long> A(N); for(auto &v:A) cin>>v; /* --- BASE 部 --- */ long long sum=0; for(auto a:A){ sum += (M-a)%MOD; if(sum>=MOD) sum-=MOD; } long long powM_N1 = mod_pow(M, N-1); long long BASE = (__int128)powM_N1*sum % MOD; if(N==1){ // スワップが無い cout<<BASE<<"\n"; return 0; } /* 区間情報 */ vector<long long> lo(N-1), hi(N-1), len(N-1); vector<int> sig(N-1); // +1,0,-1 for(int i=0;i<N-1;i++){ lo[i]=min(A[i],A[i+1]); hi[i]=max(A[i],A[i+1]); len[i]=hi[i]-lo[i]; sig[i]=(A[i]<A[i+1])?1:(A[i]>A[i+1]?-1:0); } long long Mmod = M%MOD; long long Sall = Mmod; // B1 … 何でも OK long long Sin = len[0]%MOD; // B1 が I0 の “中” /* 1 本ずつ処理 */ for(int i=0;i<N-1;i++){ long long lcur=len[i]; int s=sig[i]; long long lnext = (i==N-2)?0:len[i+1]; long long inter = 0; if(i!=N-2){ long long x=max(lo[i],lo[i+1]); long long y=min(hi[i],hi[i+1]); if(y>x) inter=y-x; // (x, y] } long long Sall_n, Sin_n=0; if(s==1){ /* 上り */ Sall_n = ( (__int128)lcur*Sin + (__int128)(M-lcur)*Sall ) % MOD; if(i!=N-2) Sin_n = ( (__int128)inter*Sin + (__int128)(lnext-inter)*Sall )%MOD; }else if(s==-1){ /* 下り */ long long Sout = (Sall - Sin + MOD)%MOD; Sall_n = ( (__int128)lcur*Sall + (__int128)(M-lcur)*Sout ) % MOD; if(i!=N-2) Sin_n = ( (__int128)inter*Sall + (__int128)(lnext-inter)*Sout )%MOD; }else{ /* 同値 */ Sall_n = (__int128)Mmod*Sall % MOD; if(i!=N-2) Sin_n = (__int128)lnext*Sall % MOD; } Sall = Sall_n; Sin = Sin_n; // advance } long long T = Sall; // 禁止パターン無しの列数 long long powM_N = (__int128)powM_N1*Mmod % MOD; long long extra = (powM_N - T + MOD) % MOD; cout << (BASE + extra) % MOD << '\n'; return 0; }