結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
![]() |
提出日時 | 2025-04-18 21:58:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 136 ms / 2,000 ms |
コード長 | 1,186 bytes |
コンパイル時間 | 4,234 ms |
コンパイル使用メモリ | 253,968 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-04-18 21:58:40 |
合計ジャッジ時間 | 13,119 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001LL int main(){ long long n,m; cin>>n>>m; vector<long long> a(n); rep(i,n)cin>>a[i]; mint ans = mint(m).pow(n); rep(i,n){ ans += mint(m).pow(n-1) * (m-a[i]); } a.push_back(m); vector<mint> dp(4); dp[0] = 1; rep(i,n){ vector<mint> ndp(4,0); rep(j,4){ rep(k,4){ int l = 1,r = m; rep(ll,2){ if((0==((k>>ll)&1))){ r = min(r,(int)a[i+ll]); } else{ l = max(l,(int)a[i+ll]+1); } } if(r-l+1<=0)continue; if(i==0){ ndp[k] += dp[j] * (r-l+1); } else{ rep(ll,2){ int tr = r,tl = l; if(ll==0)tr = min(tr,(int)a[i-1]); else tl = max(tl,(int)a[i-1]+1); if(tr-tl+1<=0)continue; int x = 0,y = 0; if(j&1)x++; if(k&1)x++; if(j&2)y++; if(ll)y++; if(x<y)continue; ndp[k] += dp[j] * (tr-tl+1); } } } } swap(dp,ndp); } rep(i,4)ans -= dp[i]; cout<<ans.val()<<endl; return 0; }