#1187632 (C++23(gnu拡張gcc16)) No.3716 Keep it Integer

• 問題: No.3716 Keep it Integer
• ユーザー: KEYBO
• 提出日時: 2026-09-18 22:18:42
• 言語: C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 745 ms / 2,000 ms
• コード長: 2,836 bytes
• コンパイル時間: 5,119 ms
• コンパイル使用メモリ: 392,948 KB
• 実行使用メモリ: 17,664 KB
• 最終ジャッジ日時: 2026-09-18 22:19:31
• 合計ジャッジ時間: 37,560 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 50

ソースコード

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

using ll = int64_t;
using ul = uint64_t;
using ld = long double;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vs = vector<string>;
using vb = vector<bool>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvd = vector<vd>;
using vvc = vector<vc>;
using vvb = vector<vb>;
using vvl = vector<vl>;
using mint = modint998244353;
using vm = vector<mint>;

template <typename X>
struct SegTree {
  using FX = function<X(X, X)>; // X○X -> Xとなる関数の型
  int N; // 葉の数
  FX fx; // 関数
  const X ex; // 単位元
  vector<X> data; // セグ木

  SegTree(int N_, FX fx_, X ex_) : N(1), fx(fx_), ex(ex_), data(N_*4, ex_) {
    while(N_ > N) N *= 2;
  }
  // 0 <= pos <= N - 1
  void set(int pos, X x) { data[pos + N - 1] = x; }
  void build() {
    for (int pos = N - 2; pos >= 0; pos--) {
      data[pos] = fx(data[pos*2 + 1], data[pos*2 + 2]);
    }
  }

  // 1点更新
  // 0 <= pos <= N - 1
  void update(int pos, X x) {
    pos += N - 1;
    data[pos] = x;
    while(pos > 0) {
      pos = (pos - 1)/2; // 親へ伝播
      data[pos] = fx(data[pos*2 + 1], data[pos*2 + 2]);
    }
  }

  // クエリ呼び出し
  // 0 <= a <= N - 1
  // 1 <= b <= N
  X query(int a, int b) {
    return query_sub(a, b, 0, 0, N);
  }

  // クエリ回答
  X query_sub(int a, int b, int pos, int l, int r) {
    // 範囲外
    if (r <= a || b <= l) return ex;
    // 完全に含まれる
    else if (a <= l && r <= b) return data[pos];
    // 一部だけ含まれる
    else return fx(query_sub(a, b, pos*2 + 1, l, (l + r)/2), query_sub(a, b, pos*2 + 2, (l + r)/2, r));
  }
};

int main() {
  /*int N;
  cin >> N;
  auto fx = [](int x1, int x2) -> int { return max(x1, x2); };
  int ex = 0;
  SegTree<int> seg(N, fx, ex);*/
  ll N,X;
  cin >> N >> X;
  vl A(N + 1);
  A[0] = X;
  for (int i = 0; i < N; i++) {
    cin >> A[i + 1];
  }
  N++;

  auto fx1 = [](ll x1, ll x2) -> ll {
    if (x1 == -1 || x2 == -1) return -1;
    else if (x2 <= 5e18/x1) return x1*x2;
    else return -1;
  };
  ll ex1 = 1;
  SegTree<ll> seg1(N, fx1, ex1);
  for (int i = 0; i < N; i++) {
    seg1.set(i, A[i]);
  }
  seg1.build();

  auto fx2 = [](ll x1, ll x2) -> ll { return (x1 + x2)%998244353; };
  ll ex2 = 0;
  SegTree<ll> seg2(N, fx2, ex2);
  seg2.set(N - 1, 1);
  seg2.build();

  ll mod = 998244353;
  for (int i = N - 2; i >= 0; i--) {
    ll l = i, r = N;
    while(l + 1 < r) {
      int m = (l + r)/2;
      ll pro = seg1.query(i + 1, m + 1);
      if (pro == -1) r = m;
      else if (A[i]%pro == 0) l = m;
      else r = m;
    }
    ll now = seg2.query(i + 1, min(r + 1, N))%mod;
    if (r == N) now = (now + 1)%mod;
    seg2.update(i, now);
  }
  cout << seg2.query(0, 1) << endl;
  return 0;
}