#1138148 (C++17) No.3396 ChRisTmas memory

• 問題: No.3396 ChRisTmas memory
• ユーザー: i_am_noob
• 提出日時: 2025-12-03 01:00:59
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,034 ms / 4,000 ms
• コード長: 14,311 bytes
• コンパイル時間: 4,829 ms
• コンパイル使用メモリ: 232,716 KB
• 実行使用メモリ: 7,852 KB
• 最終ジャッジ日時: 2025-12-03 01:01:18
• 合計ジャッジ時間: 15,991 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 2
other	AC * 40

ソースコード

// BEGIN: main.cpp
#line 1 "main.cpp"
#include<bits/stdc++.h>
using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define sz(a) ((int)a.size())

using ll=long long;
using u32=unsigned int;
using u64=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using f128=__float128;

using pii=pair<int,int>;
using pll=pair<ll,ll>;

template<typename T> using vc=vector<T>;
template<typename T> using vvc=vc<vc<T>>;
template<typename T> using vvvc=vc<vvc<T>>;

using vi=vc<int>;
using vll=vc<ll>;
using vvi=vc<vi>;
using vvll=vc<vll>;

#define vv(type,name,n,...) \
    vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
#define vvv(type,name,n,m,...) \
    vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))

template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
template<typename T> using max_heap=priority_queue<T>;

// https://trap.jp/post/1224/
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))

template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);}
template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);}

template<typename T>
void sort_unique(vector<T> &vec){
    sort(vec.begin(),vec.end());
    vec.resize(unique(vec.begin(),vec.end())-vec.begin());
}

template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;}
template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;}

template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;}
template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;}

#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}

template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;}

vvi read_graph(int n, int m, int base=1){
    vvi adj(n);
    for(int i=0,u,v; i<m; ++i){
        cin >> u >> v,u-=base,v-=base;
        adj[u].pb(v),adj[v].pb(u);
    }
    return adj;
}

vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);}

template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};}

template<typename T> constexpr T inf=0;
template<> constexpr int inf<int> = 0x3f3f3f3f;
template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f;

template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;}

template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;}

#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())

//#include<atcoder/all>
//using namespace atcoder;

//using mint=modint998244353;
//using mint=modint1000000007;

// BEGIN: library/nt/extgcd.hpp
#line 1 "library/nt/extgcd.hpp"

// ax + by = gcd(a,b), {gcd(a,b),x,y}
template<typename T>
array<T,3> extgcd(T a, T b){
    T x1=1,y1=0,x2=0,y2=1;
    while(b!=0){
        T q=a/b;
        a%=b;
        swap(a,b);
        T x3=x1-x2*q,y3=y1-y2*q;
        x1=x2,y1=y2,x2=x3,y2=y3;
    }
    return {a,x1,y1};
}

template<typename T>
T modinv(T x, T m){
    auto [g,val1,val2]=extgcd<T>(x,m);
    assert(g==1);
    if(val1<0) val1+=m;
    return val1;
}// END: library/nt/extgcd.hpp
#line 113 "main.cpp"
// BEGIN: library/nt/pollard_rho.hpp
#line 1 "library/nt/pollard_rho.hpp"

// BEGIN: library/nt/binary_gcd.hpp
#line 1 "library/nt/binary_gcd.hpp"

template<typename T>
T bgcd(T a, T b){
    if(a==0) return b;
    if(b==0) return a;
    int az=__builtin_ctzll(a);
    int bz=__builtin_ctzll(b);
    int shift=min(az,bz);
    b>>=bz;
    while(a!=0){
        a>>=az;
        T diff=b-a;
        az=__builtin_ctzll(diff);
        b=min(a,b);
        a=abs(diff);
    }
    return b<<shift;
}// END: library/nt/binary_gcd.hpp
#line 4 "library/nt/pollard_rho.hpp"
// BEGIN: library/nt/miller_rabin.hpp
#line 1 "library/nt/miller_rabin.hpp"

// BEGIN: library/mod/montgomery_modint.hpp
#line 1 "library/mod/montgomery_modint.hpp"

#line 4 "library/mod/montgomery_modint.hpp"

// arbitrary modint, odd mod
// stores x*(2^K) mod m
// https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod
// https://judge.yosupo.jp/problem/primality_test (used by miller rabin)
template<int id, bool is_prime, int K, typename word, typename dword, typename signed_word> // support multiple modulos at the same time
struct montgomery_modint{
    using mint=montgomery_modint;

    inline static word m,r,val64,m2; // m = modulo < 2^(K-2), r = (-m^(-1)) (mod 2^K), val64 = (2^(2K)) (mod m), m2 = 2m

    static void set_mod(word _m){
        assert((_m&1)&&_m<(word(1)<<(K-2)));
        m=_m,r=m,val64=(-dword(m))%m,m2=m*2;
        // use Newton's method to calculate p^(-1) (mod 2^K)
        // starts from p = p^(-1) (mod 4)
        for(int i=0; i<5; ++i) r*=2-m*r;
        r=-r;
        assert(r*m==word(-1));
    }
    static int get_mod(){
        return m;
    }

    word x;

    montgomery_modint():x(0){}
    montgomery_modint(int64_t _x):x(reduce(dword((_x%m+m)%m)*val64)){}

    word reduce(const dword &y) const {
        // (y + (yr mod 2^K)*p) / (2^K)
        // 0 <= return < 2p
        return (y+dword(word(y)*r)*m)>>K;
    }

    mint operator += (const mint &o){
        x+=o.x;
        if(x>=m2) x-=m2;
        return *this;
    }
    mint operator -= (const mint &o){
        x-=o.x;
        if(int32_t(x)<0) x+=m2;
        return *this;
    }
    mint operator *= (const mint &o){
        x=reduce(dword(x)*o.x);
        return *this;
    }
    mint operator /= (const mint &o){
        return (*this)*=o.inv();
    }
    mint operator + (const mint &o) const {return mint(*this)+=o;}
    mint operator - (const mint &o) const {return mint(*this)-=o;}
    mint operator * (const mint &o) const {return mint(*this)*=o;}
    mint operator / (const mint &o) const {return mint(*this)/=o;}
    mint operator - () const {return mint(0)-*this;}
    mint pow(int64_t n) const {
        assert(n>=0);
        mint res=1,b=*this;
        for(; n; n>>=1,b*=b) if(n&1) res*=b;
        return res;
    }
    inline mint inv1() const {
        return pow(m-2);
    }
    inline mint inv2() const {
        auto [g,val1,val2]=extgcd<signed_word>(get(),m);
        assert(g==1);
        return mint(val1);
    }
    mint inv() const {
        if(is_prime) return inv1();
        return inv2();
    }

    bool operator == (const mint &o) const {
        return (x>=m?x-m:x)==(o.x>=m?o.x-m:o.x);
    }
    bool operator != (const mint &o) const {
        return (x>=m?x-m:x)!=(o.x>=m?o.x-m:o.x);
    }

    word get() const {
        word res=reduce(x);
        return res>=m?res-m:res;
    }

    friend istream& operator >> (istream& is, mint &b){
        int64_t y;
        is >> y;
        b=mint(y);
        return is;
    }
    friend ostream& operator << (ostream& os, const mint &b){
        return os << b.get();
    }
};

template<int id, bool is_prime> using montgomery_modint_32=montgomery_modint<id,is_prime,32,uint32_t,uint64_t,int32_t>;
template<int id, bool is_prime> using montgomery_modint_64=montgomery_modint<id,is_prime,64,uint64_t,unsigned __int128,int64_t>;// END: library/mod/montgomery_modint.hpp
#line 4 "library/nt/miller_rabin.hpp"

// https://judge.yosupo.jp/problem/primality_test
bool is_prime(ll x){
    if(x<2) return false;
    static const vector<int> small={2,3,5,7,11,13,17,19};
    for(int p: small){
        if(x==p) return true;
        if(x%p==0) return false;
    }
    if(x<400) return true;
    assert(x<(1ll<<62));
    ll d=x-1;
    int s=0;
    while(d%2==0) d>>=1,s++;
    using mint=montgomery_modint_64<777771449,false>;
    mint::set_mod(x);
    const mint zero(0),one(1),minus_one(x-1);
    auto check=[&](ll _a) -> bool{
        mint a=mint(_a).pow(d);
        if(a==one||a==zero) return true;
        for(int i=0; i<s; ++i,a*=a){
            if(a==one) return false;
            if(a==minus_one) return true;
        }
        return false;
    };
    if(x<(1ll<<32)){
        for(ll a: {2,7,61}){
            if(!check(a)) return false;
        }
    }
    else{
        for(ll a: {2,325,9375,28178,450775,9780504,1795265022}){
            if(!check(a)) return false;
        }
    }
    return true;
}// END: library/nt/miller_rabin.hpp
#line 5 "library/nt/pollard_rho.hpp"

// https://judge.yosupo.jp/problem/factorize
struct pollard_rho{
    ll find_factor(ll n){
        if(n<=1||is_prime(n)) return 1;
        static const vector<int> small={2,3,5,7,11,13,17,19};
        for(int p: small){
            if(n%p==0) return p;
        }
        using mint=montgomery_modint_64<777771449,false>;
        mint::set_mod(n);
        mint x,y(2),d,t(1);
        auto f=[&](mint a){return a*a+t;};
        for(int l=2; ; l<<=1){
            x=y;
            int m=min(l,32);
            for(int i=0; i<l; i+=m){
                d=1;
                for(int j=0; j<m; ++j){
                    y=f(y);
                    d*=x-y;
                }
                ll g=bgcd<ll>(d.get(),n);
                if(g==n){
                    l=1,y=2,t+=1;
                    break;
                }
                if(g!=1) return g;
            }
        }
    }
    map<ll,int> mp;
    void dfs(ll n){
        if(n<=1) return;
        if(is_prime(n)) return mp[n]++,void();
        ll d=find_factor(n);
        dfs(d);
        dfs(n/d);
    }
};

vector<pair<ll,int>> factorize(ll n){
    pollard_rho tmp;
    tmp.dfs(n);
    vector<pair<ll,int>> res;
    for(auto [x,y]: tmp.mp){
        res.pb({x,y});
    }
    return res;
}

vector<ll> find_all_divisors(ll n){
    vector<pair<ll,int>> vec=factorize(n);
    vector<ll> res;
    auto dfs=[&](auto &self, int i, ll cur){
        if(i==(int)vec.size()){
            res.pb(cur);
            return;
        }
        for(int j=0; j<vec[i].second; ++j){
            self(self,i+1,cur);
            cur*=vec[i].first;
        }
        self(self,i+1,cur);
    };
    dfs(dfs,0,1);
    sort(res.begin(),res.end());
    return res;
}// END: library/nt/pollard_rho.hpp
#line 114 "main.cpp"

int get(int a, int b, int m){
    // ax=b (mod m)
    if(b==0) return 0;
    if(a==0) return -1;
    int g=__gcd(__gcd(a,b),m);
    a/=g,b/=g,m/=g;
    if(__gcd(a,m)!=1) return -1;
    int x=modinv<int>(a,m);
    return 1ll*b*x%m;
}

void mango(){
    vi M,R;
    map<int,vi> mp;
    vi x,y;
    vvi nw;
    int dead=inf<int>;

    auto ins=[&](int m, int r){
        if(dead<sz(M)){
            M.pb(-1),R.pb(-1);
            x.pb(-1),y.pb(-1);
            nw.pb({});
            return;
        }
        int now=0,cur=1;
        rep(sz(M)){
            now=(now+1ll*cur*y[i])%m;
            cur=1ll*cur*x[i]%m;
        }
        int val=get(cur,(r-now+m)%m,m);
        if(val==-1){
            dead=sz(M);
            M.pb(-1),R.pb(-1);
            x.pb(-1),y.pb(-1);
            nw.pb({});
            return;
        }
        nw.pb({});
        vc<pair<ll,int>> f=factorize(m);
        x.pb(1),y.pb(val);
        for(auto [p,cnt]: f){
            if(mp.count(p)){
                if(cnt>mp[p].back()){
                    rep(_,cnt-mp[p].back()){
                        x.back()*=p;
                    }
                    mp[p].pb(cnt);
                    nw.back().pb(p);
                }
            }
            else{
                rep(_,cnt) x.back()*=p;
                mp[p].pb(cnt);
                nw.back().pb(p);
            }
        }
        M.pb(m),R.pb(r);
    };
    auto pop=[&](){
        if(dead<sz(M)){
            if(dead==sz(M)-1) dead=inf<int>;
            M.pop_back(),R.pop_back(),x.pop_back(),y.pop_back(),nw.pop_back();
            return;
        }
        for(auto p: nw.back()){
            mp[p].pop_back();
            if(mp[p].empty()) mp.erase(p);
        }
        M.pop_back(),R.pop_back(),x.pop_back(),y.pop_back(),nw.pop_back();
    };
    auto query=[&](int m){
        if(dead<sz(M)) return -1;
        int now=0,cur=1;
        rep(sz(M)){
            bug(M[i],R[i],x[i],y[i]);
            now=(now+1ll*cur*y[i])%m;
            cur=1ll*cur*x[i]%m;
        }
        return now;
    };
    int q; cin >> q;
    while(q--){
        int op; cin >> op;
        if(op==1){
            int m,r; cin >> m >> r;
            ins(m,r);
        }
        else if(op==2){
            int k; cin >> k;
            rep(k) pop();
        }
        else{
            int m; cin >> m;
            print(query(m));
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cout << fixed << setprecision(20);
    int t=1;
    //cin >> t;
    while(t--) mango();
}
// END: main.cpp