#1042911 (C++17) No.3026 Range LCM (Online Version)

提出ソース
結果

問題	No.3026 Range LCM (Online Version)
コンテスト
ユーザー	Nachia
提出日時	2025-02-14 22:24:00
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,301 ms / 3,000 ms
コード長	11,345 bytes
コンパイル時間	2,056 ms
コンパイル使用メモリ	118,620 KB
実行使用メモリ	61,100 KB
最終ジャッジ日時	2025-09-06 00:45:17
合計ジャッジ時間	39,138 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 37
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#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; }
    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
#include <cstdint>

namespace nachia{

int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x88888888;
    constexpr u64 mi = 0x11111111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}


namespace nachia{

template<class PosX, class PosY>
struct TwoDRectangleQuery{
private:

struct BitVectorRank {
    using u64 = std::uint64_t;
    using u32 = std::uint32_t;
    
    std::vector<std::pair<u64, u32>> a;
    BitVectorRank(const std::vector<bool>& b = {}){
        int n = b.size();
        a.assign(n/64 + 1, std::make_pair((u64)0, (u32)0));
        auto p = b.begin();
        u32 sum = 0;
        u64 tmp = 0;
        for(int i=0; i<=n; i+=64){
            tmp = 0;
            int maxd = std::min<int>(n - i, 64);
            for(int d=0; d<maxd; d++){
                tmp |= (u64)(*p ? 1 : 0) << d;
                ++p;
            }
            a[i/64] = std::make_pair(tmp, sum);
            sum += Popcount(tmp);
        }
    }
    std::uint32_t rank(std::uint32_t i) const {
        auto [b, s] = a[i >> 6];
        return (u32)(Popcount(b & ~(~u64(0) << (i & 63)))) + s;
    }
    bool get(std::uint32_t i) const { return (a[i >> 6].first >> (i & 63)) & 1; }
};
    
    int n;
    int N;
    int logN;
    std::vector<PosX> Xsorted;
    std::vector<PosY> Ysorted;
    std::vector<int> rankX;
    std::vector<std::vector<int>> Idx;
    std::vector<int> Z;
    std::vector<BitVectorRank> L;

public:

    TwoDRectangleQuery(){}

    TwoDRectangleQuery(const std::vector<std::pair<PosX, PosY>>& pos){
        n = pos.size();

        std::vector<int> sortIY(n);
        for(int i=0; i<n; i++) sortIY[i] = i;
        std::sort(sortIY.begin(),sortIY.end(),[&pos](int l,int r){ return pos[l].second<pos[r].second; });
        Ysorted.resize(n);
        for(int i=0; i<n; i++) Ysorted[i] = pos[sortIY[i]].second;

        std::vector<int> sortIX(n);
        rankX.resize(n);
        for(int i=0; i<n; i++) sortIX[i] = i;
        std::sort(sortIX.begin(),sortIX.end(),[&pos](int l,int r){ return pos[l]<pos[r]; });
        Xsorted.resize(n);
        for(int i=0; i<n; i++) Xsorted[i] = pos[sortIX[i]].first;
        for(int i=0; i<n; i++) rankX[sortIX[i]] = i;

        N = 1; logN = 0;
        while(N < n){ N *= 2; logN++; }
        Idx.assign(logN+1, std::vector<int>(n,-1));
        L.resize(logN);
        Z.resize(logN);
        for(int i=0; i<n; i++) Idx.back()[i] = sortIY[i];
        for(int i=logN-1; i>=0; i--){
            std::vector<bool> Lbuf(n,0);
            auto& preList = Idx[i+1];
            int z = ((n >> (i+1)) << i) + std::min(1<<i, (n % (2 << i)));
            Z[i] = z;
            int ai = 0, bi = z;
            for(int k=0; k<n; k++){
                bool chooseb = rankX[preList[k]] & (1<<i);
                if(!chooseb) Idx[i][ai++] = preList[k];
                else Idx[i][bi++] = preList[k];
                Lbuf[k] = !chooseb;
            }
            L[i] = BitVectorRank(Lbuf);
        }

        for(int i=0; i<n; i++) rankX[sortIY[i]] = i;
    }
 
    int getSegmentCount() const { return Idx.size(); }
    int size() const { return n; }
    int toVtx(int d, int i) const { return Idx[d][i]; }


    struct UpdatePoint{ int d, i; };

    std::vector<UpdatePoint> getUpdatePoints(int v) const {
        std::vector<UpdatePoint> res(logN+1);
        int p = rankX[v];
        int d = logN;
        while(d > 0){
            res[d] = { d,p };
            d--;
            if(L[d].get(p)) p = L[d].rank(p);
            else p = Z[d] + p - L[d].rank(p);
        }
        res[d] = {d,p};
        return res;
    }


    struct Query{ int d,l,r; };
    std::vector<Query> getRangesFromIdx(int xl, int xr, int yl, int yr) const {
        if(xl >= xr || yl >= yr) return {};
        std::vector<Query> res;
        struct Search{ int i, xa, xb, ys, yt; };
        std::vector<Search> Q;
        res.reserve((logN+1)*2);
        Q.reserve((logN+1)*2);
        Q.push_back({ logN,0,n,yl,yr });
        for(int i=0; i<(int)Q.size(); i++){
            auto p = Q[i];
            if(p.xa == p.xb) continue;
            if(xl <= p.xa && p.xb <= xr){
                res.push_back({ p.i, p.ys, p.yt });
                continue;
            }
            p.i--;
            int nxs = L[p.i].rank(p.ys), nxt = L[p.i].rank(p.yt);
            int xm = p.xa+(1<<p.i);
            if(xl < xm) Q.push_back({ p.i,p.xa,xm,nxs,nxt });
            if(xm < xr) Q.push_back({ p.i,xm,p.xb,Z[p.i]+p.ys-nxs,Z[p.i]+p.yt-nxt });
        }
        return res; 
    }
  
    std::vector<Query> getRanges(PosX xl, PosX xr, PosY yl, PosY yr) const {
        return getRangesFromIdx(
            lower_bound(Xsorted.begin(),Xsorted.end(),xl) - Xsorted.begin(),
            lower_bound(Xsorted.begin(),Xsorted.end(),xr) - Xsorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yl) - Ysorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yr) - Ysorted.begin()
        );
    }
};

} // namespace nachia
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(i64 i=0; i<i64(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;
using mint = nachia::StaticModint<998244353>;

using Bitset = bitset<112>;
struct RangeOr {
    int n;
    int N;
    vector<Bitset> A;
    RangeOr(vector<Bitset> f){
        n = int(f.size());
        N = 1;
        while(N <= i64(f.size())) N *= 2;
        A.assign(N*2, Bitset());
        rep(i,f.size()) A[N+i] = f[i];
        for(i64 i=N-1; i>=1; i--) A[i] = A[i*2] | A[i*2+1];
    }
    Bitset prod(int l, int r){
        l += N; r += N;
        Bitset res;
        while(l < r){
            if(l%2) res |= A[l++];
            if(r%2) res |= A[--r];
            l /= 2; r /= 2;
        }
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int Z = 200000;
    vector<int> contribute(Z+1);
    vector<vector<int>> pf(Z+1);
    for(int p=2; p<=Z; p++) if(pf[p].empty()){
        for(int pp=p; ; pp*=p){
            contribute[pp] = p;
            for(int q=1; pp*q<=Z; q++){
                pf[pp*q].push_back(pp);
            }
            if(i64(pp)*p > Z) break;
        }
    }
    const int th = 128;
    int N; cin >> N;
    vector<int> A(N); rep(i,N) cin >> A[i];
    vector<Bitset> fairy(N);
    vector<mint> cfairy;
    rep(i,Z+1) if(contribute[i] != 0 && contribute[i] < th){
        int d = cfairy.size();
        rep(p,N) if(A[p] % i == 0) fairy[p].set(d);
        cfairy.push_back(contribute[i]);
    }
    auto fairyds = RangeOr(move(fairy));
    vector<pair<int,int>> points;
    vector<mint> V;
    vector<int> P(Z+1, -1);
    rep(i,N){
        int a = A[i];
        int b = 1;
        for(int pp : pf[a]) if(contribute[pp] >= th){
            if(P[pp] != -1){
                points.push_back({ P[pp], i });
                V.push_back(contribute[pp]);
            }
            P[pp] = i;
            b *= contribute[pp];
        }
        A[i] = b;
    }
    vector<mint> prod(N+1); prod[0] = 1;
    rep(i,N) prod[i+1] = prod[i] * A[i];
    auto md = nachia::TwoDRectangleQuery<int,int>(points);
    vector<vector<mint>> F(md.getSegmentCount(), vector<mint>(points.size()+1));
    rep(i,F.size()){
        F[i][0] = 1;
        rep(j,points.size()) F[i][j+1] = F[i][j] * V[md.toVtx(i,j)];
    }
    int Q; cin >> Q;
    mint ans = 1;
    rep(qi,Q){
        int a,b; cin >> a >> b;
        int l = (ans * mint(a)).val() % N;
        int r = (ans * mint(b)).val() % N;
        if(l > r) swap(l, r);
        r += 1;
        mint p = 1;
        mint q = 1;
        auto fr = fairyds.prod(l,r);
        rep(i,fr.size()) if(fr.test(i)) p *= cfairy[i];
        p *= prod[r];
        q *= prod[l];
        for(auto [d,ll,rr] : md.getRanges(l,r,l,r)){
            q *= F[d][rr];
            p *= F[d][ll];
        }
        ans = p / q;
        cout << ans.val() << "\n";
    }
    return 0;
}
yukicoder

結果

ソースコード
