結果

問題 No.3119 A Little Cheat
ユーザー Nzt3
提出日時 2025-03-19 22:55:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 54 ms / 2,000 ms
コード長 4,081 bytes
コンパイル時間 3,452 ms
コンパイル使用メモリ 282,284 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-17 01:12:18
合計ジャッジ時間 7,344 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define ov4(a, b, c, d, name, ...) name
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for (ll i = (a) - 1; i >= (b); i--)
#define fore(e, v) for (auto&& e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template <typename T, typename S>
bool chmin(T& a, const S& b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
bool chmax(T& a, const S& b) {
  return a < b ? a = b, 1 : 0;
}
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
  _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

constexpr int MOD = 998244353;

void ch(ll& a, ll b) { a = (a + b) % MOD; }

int main() {
  ll N, M;
  cin >> N >> M;
  vl A(N);
  fore(i, A) cin >> i;
  A.eb(0);
  using apll4 = array<pll, 4>;
  using al4 = array<ll, 4>;
  apll4 dp;
  dp[3] = pll{0, 0};
  if (A[0] < A[1]) {
    dp[0] = pll{A[0], 0};
    dp[1] = pll{A[1] - A[0], A[1] - A[0]};
    dp[2] = pll{M - A[1], M - A[1]};
  } else {
    dp[0] = pll{A[1], 0};
    dp[1] = pll{A[0] - A[1], 0};
    dp[2] = pll{M - A[0], M - A[0]};
  }

  rep(i, 1, N) {
    apll4 ndp;
    rep(i, 4) ndp[i] = pll{0, 0};
    ch(ndp[3].first, dp[3].first * M);
    ch(ndp[3].second, dp[3].second * M + dp[3].first * (M - A[i]));
    al4 m1{0ll, min(A[i - 1], A[i]), max(A[i - 1], A[i]), M};
    al4 m2{0ll, min(A[i], A[i + 1]), max(A[i], A[i + 1]), M};
    if (A[i - 1] < A[i]) {
      // swap: (2,1),(0,1)
      // +1  : (0,2),(1,2),(2,2)
      // none: (0,0),(1,0),(1,1),(2,0)
      rep(j, 3) {
        rep(k, 3) {
          if ((j == 0 && k == 1) || (j == 2 && k == 1)) {
            rep(l, 3) {
              ll t = max(0ll, min(m1[k + 1], m2[l + 1]) - max(m1[k], m2[l]));
              ch(ndp[3].first, dp[j].first * t);
              ch(ndp[3].second, dp[j].second * t + dp[j].first * t);
            }
          } else if (k == 2) {
            rep(l, 3) {
              ll t = max(0ll, min(m1[k + 1], m2[l + 1]) - max(m1[k], m2[l]));
              ch(ndp[l].first, dp[j].first * t);
              ch(ndp[l].second, dp[j].second * t + dp[j].first * t);
            }
          } else {
            rep(l, 3) {
              ll t = max(0ll, min(m1[k + 1], m2[l + 1]) - max(m1[k], m2[l]));
              ch(ndp[l].first, dp[j].first * t);
              ch(ndp[l].second, dp[j].second * t);
            }
          }
        }
      }
    } else {
      // swap: (1,0),(1,2)
      // +1  : (0,1),(0,2),(1,1),(1,2),(2,2)
      // none: (0,0),(2,0)
      rep(j, 3) {
        rep(k, 3) {
          if ((j == 1 && k == 0) || (j == 1 && k == 2)) {
            rep(l, 3) {
              ll t = max(0ll, min(m1[k + 1], m2[l + 1]) - max(m1[k], m2[l]));
              ch(ndp[3].first, dp[j].first * t);
              ch(ndp[3].second,
                 dp[j].second * t + dp[j].first * t * (1 + (k == 2)));
            }
          } else if (k >= 1) {
            rep(l, 3) {
              ll t = max(0ll, min(m1[k + 1], m2[l + 1]) - max(m1[k], m2[l]));
              ch(ndp[l].first, dp[j].first * t);
              ch(ndp[l].second, dp[j].second * t + dp[j].first * t);
            }
          } else {
            rep(l, 3) {
              ll t = max(0ll, min(m1[k + 1], m2[l + 1]) - max(m1[k], m2[l]));
              ch(ndp[l].first, dp[j].first * t);
              ch(ndp[l].second, dp[j].second * t);
            }
          }
        }
      }
    }
    dp = ndp;
  }
  ll ans = 0, cnt = 0;
  rep(i, 4) ch(ans, dp[i].second);
  rep(i, 4) ch(cnt, dp[i].first);
  cout << ans << '\n';
  // cerr<<cnt<<'\n';
  // rep(i,4)cerr<<dp[i].first<<' ';
  // cerr<<endl;
  // rep(i,4)cerr<<dp[i].second<<' ';
  // cerr<<endl;
}
0