#1187532 (C++17) No.3716 Keep it Integer

• 問題: No.3716 Keep it Integer
• ユーザー: 👑 Nachia
• 提出日時: 2026-09-18 21:44:18
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,683 bytes
• コンパイル時間: 564 ms
• コンパイル使用メモリ: 102,280 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-18 21:44:29
• 合計ジャッジ時間: 5,368 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 31 WA * 19

ソースコード

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }


#include <utility>

#include <cassert>
namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    bool operator==(const my_type& r) const { return x == r.x; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const { return x; }
    int hval() const { return int(x > MOD/2 ? x - MOD : x); }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia
using Mint = nachia::StaticModint<998244353>;

namespace nachia {

template <class T> struct FenwickTree {
public:
    FenwickTree() : _n(0){}
    explicit FenwickTree(int n, T ZERO = T(0)) : _n(n), a(n, ZERO){}
    void add(int p, T x){
        assert(0 <= p && p < _n);
        p++;
        while(p <= _n){
            a[p-1] += T(x);
            p += p & -p;
        }
    }
    T sum(int r){
        return sumr(r);
    }
    T sum(int l, int r){
        return sumr(r) - sumr(l);
    }
private:
    int _n;
    std::vector<T> a;

    T sumr(int r){
        T s = 0;
        while(r > 0){
            s += a[r-1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace nachia

namespace nachia {
    template<class T> using PointAddRangeSumFwt = FenwickTree<T>;
} // namespace nachia

void testcase(){
  ll N, X; cin >> N >> X;
  V<pair<ll,ll>> st;
  V<ll> A(N);
  REP(i,N) cin >> A[i];
  A.insert(A.begin(), X); N++;
  auto getat = [&](ll a) -> ll {
    ll ok = -1, ng = st.size();
    while(ok + 1 < ng){
      ll w = ok + (ng - ok) / 2;
      if(a % st[w].first == 0) ok = w; else ng = w;
    }
    if(ng == st.size()) return N;
    return st[ng].second;
  };
  nachia::PointAddRangeSumFwt<Mint> ds(N+1);
  // for(auto a : A) cout << a << " "; cout << endl;
  ds.add(N, 1);
  for(ll i=N-1; i>=0; i--){
    ll p = getat(A[i]);
    ds.add(i, ds.sum(0, p+1));
    // cout << "i = " << i << " , p = " << p << endl;
    if(A[i] != 1){
      st.insert(st.begin(), { 1, i });
      for(ll j=(ll)st.size()-1; j>=0; j--){
        if(INF / st[j].first < A[i]){
          st.pop_back();
        } else {
          st[j].first *= A[i];
        }
      }
    }
  }
  cout << ds.sum(0, 1).val() << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}