#930216 (C++17) No.2578 Jewelry Store

提出ソース

結果

問題	No.2578 Jewelry Store
ユーザー	tko919
提出日時	2023-11-22 10:35:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,461 ms / 3,500 ms
コード長	13,993 bytes
コンパイル時間	4,206 ms
コンパイル使用メモリ	223,664 KB
実行使用メモリ	7,424 KB
最終ジャッジ日時	2023-12-05 23:34:05
合計ジャッジ時間	13,092 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	10 ms 6,676 KB
testcase_03	AC	6 ms 6,676 KB
testcase_04	AC	30 ms 6,676 KB
testcase_05	AC	6 ms 6,676 KB
testcase_06	AC	10 ms 6,676 KB
testcase_07	AC	30 ms 6,676 KB
testcase_08	AC	6 ms 6,676 KB
testcase_09	AC	30 ms 6,676 KB
testcase_10	AC	60 ms 6,676 KB
testcase_11	AC	6 ms 6,676 KB
testcase_12	AC	6 ms 6,676 KB
testcase_13	AC	6 ms 6,676 KB
testcase_14	AC	6 ms 6,676 KB
testcase_15	AC	5 ms 6,676 KB
testcase_16	AC	59 ms 6,676 KB
testcase_17	AC	30 ms 6,676 KB
testcase_18	AC	5 ms 6,676 KB
testcase_19	AC	17 ms 6,676 KB
testcase_20	AC	30 ms 6,676 KB
testcase_21	AC	31 ms 6,676 KB
testcase_22	AC	9 ms 6,676 KB
testcase_23	AC	18 ms 6,676 KB
testcase_24	AC	9 ms 6,676 KB
testcase_25	AC	12 ms 6,676 KB
testcase_26	AC	9 ms 6,676 KB
testcase_27	AC	177 ms 6,676 KB
testcase_28	AC	293 ms 6,676 KB
testcase_29	AC	276 ms 6,676 KB
testcase_30	AC	362 ms 6,676 KB
testcase_31	AC	191 ms 6,676 KB
testcase_32	AC	120 ms 6,676 KB
testcase_33	AC	160 ms 6,676 KB
testcase_34	AC	195 ms 6,676 KB
testcase_35	AC	49 ms 6,676 KB
testcase_36	AC	163 ms 6,676 KB
testcase_37	AC	55 ms 6,676 KB
testcase_38	AC	83 ms 6,676 KB
testcase_39	AC	71 ms 6,676 KB
testcase_40	AC	81 ms 6,676 KB
testcase_41	AC	66 ms 6,676 KB
testcase_42	AC	55 ms 6,676 KB
testcase_43	AC	127 ms 6,676 KB
testcase_44	AC	47 ms 6,676 KB
testcase_45	AC	96 ms 6,676 KB
testcase_46	AC	68 ms 6,676 KB
testcase_47	AC	700 ms 6,676 KB
testcase_48	AC	294 ms 7,424 KB
testcase_49	AC	1,461 ms 6,676 KB
testcase_50	AC	1,351 ms 6,676 KB
testcase_51	AC	64 ms 6,676 KB
testcase_52	AC	392 ms 6,676 KB
testcase_53	AC	23 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) lower_bound(ALL(v),(x))-(v).begin()
#define UB(v,x) upper_bound(ALL(v),(x))-(v).begin()

using ll=long long int;
using ull=unsigned long long;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>

class FastIO{
    static constexpr int L=1<<16;
    char rdbuf[L];
    int rdLeft=0,rdRight=0;
    inline void reload(){
        int len=rdRight-rdLeft;
        memmove(rdbuf,rdbuf+rdLeft,len);
        rdLeft=0,rdRight=len;
        rdRight+=fread(rdbuf+len,1,L-len,stdin);
    }
    inline bool skip(){
        for(;;){
            while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
            if(rdLeft==rdRight){
                reload();
                if(rdLeft==rdRight)return false;
            }
            else break;
        }
        return true;
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__int128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    inline bool _read(__uint128_t& x){
        if(!skip())return false;
        if(rdLeft+40>=rdRight)reload();
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        return true;
    }
    template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        if(rdbuf[rdLeft]!='.')return true;
        rdLeft++;
        T base=.1;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x+=base*(rdbuf[rdLeft++]^48);
            base*=.1;
        }
        if(neg)x=-x;
        return true;
    }
    inline bool _read(char& x){
        if(!skip())return false;
        if(rdLeft+1>=rdRight)reload();
        x=rdbuf[rdLeft++];
        return true;
    }
    inline bool _read(string& x){
        if(!skip())return false;
        for(;;){
            int pos=rdLeft;
            while(pos<rdRight and rdbuf[pos]>' ')pos++;
            x.append(rdbuf+rdLeft,pos-rdLeft);
            if(rdLeft==pos)break;
            rdLeft=pos;
            if(rdLeft==rdRight)reload();
            else break;
        }
        return true;
    }
    template<typename T>inline bool _read(vector<T>& v){
        for(auto& x:v){
            if(!_read(x))return false;
        }
        return true;
    }

    char wtbuf[L],tmp[50];
    int wtRight=0;
    inline void flush(){
        fwrite(wtbuf,1,wtRight,stdout);
        wtRight=0;
    }
    inline void _write(const char& x){
        if(wtRight>L-32)flush();
        wtbuf[wtRight++]=x;
    }
    inline void _write(const string& x){
        for(auto& c:x)_write(c);
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
        if(wtRight>L-32)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
                switch (sizeof(x)) {
                case 2: _write("32768"); return;
                case 4: _write("2147483648"); return;
                case 8: _write("9223372036854775808"); return;
                }
            }
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__int128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    inline void _write(__uint128_t x){
        if(wtRight>L-40)flush();
        if(x==0){
            _write('0');
            return;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    template<typename T>inline void _write(const vector<T>& v){
        rep(i,0,v.size()){
            if(i)_write(' ');
            _write(v[i]);
        }
    }
public:
    FastIO(){}
    ~FastIO(){flush();}
    inline void read(){}
    template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
        assert(_read(head));
        read(tail...); 
    }
    template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
    template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
        if(space)_write(' ');
        _write(head);
        write<ln,true>(tail...); 
    }
};

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"

#line 2 "library/Math/modint.hpp"

template<int mod=1000000007>struct fp {
    int v;
    static constexpr int get_mod(){return mod;}
    int inv() const{
        int tmp,a=v,b=mod,x=1,y=0;
        while(b)tmp=a/b,a-=tmp*b,swap(a,b),x-=tmp*y,swap(x,y);
        if(x<0){x+=mod;} return x;
    }
    fp(ll x=0){init(x%mod+mod);}
    fp& init(ll x){v=(x<mod?x:x-mod); return *this;}
    fp operator-()const{return fp()-*this;}
    fp pow(ll t){assert(t>=0); fp res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;} return res;}
    fp& operator+=(const fp& x){return init(v+x.v);}
    fp& operator-=(const fp& x){return init(v+mod-x.v);}
    fp& operator*=(const fp& x){v=ll(v)*x.v%mod; return *this;}
    fp& operator/=(const fp& x){v=ll(v)*x.inv()%mod; return *this;}
    fp operator+(const fp& x)const{return fp(*this)+=x;}
    fp operator-(const fp& x)const{return fp(*this)-=x;}
    fp operator*(const fp& x)const{return fp(*this)*=x;}
    fp operator/(const fp& x)const{return fp(*this)/=x;}
    bool operator==(const fp& x)const{return v==x.v;}
    bool operator!=(const fp& x)const{return v!=x.v;}
    friend istream& operator>>(istream& is,fp& x){return is>>x.v;}
    friend ostream& operator<<(ostream& os,const fp& x){return os<<x.v;}
};

/**
 * @brief Modint
 */
#line 5 "sol.cpp"
using Fp=fp<998244353>;

#line 2 "library/Math/miller.hpp"

struct m64 {
    using i64 = int64_t;
    using u64 = uint64_t;
    using u128 = __uint128_t;

    static u64 mod;
    static u64 r;
    static u64 n2;

    static u64 get_r() {
        u64 ret = mod;
        rep(_,0,5) ret *= 2 - mod * ret;
        return ret;
    }

    static void set_mod(u64 m) {
        assert(m < (1LL << 62));
        assert((m & 1) == 1);
        mod = m;
        n2 = -u128(m) % m;
        r = get_r();
        assert(r * mod == 1);
    }
    static u64 get_mod() { return mod; }

    u64 a;
    m64() : a(0) {}
    m64(const int64_t &b) : a(reduce((u128(b) + mod) * n2)){};

    static u64 reduce(const u128 &b) {
        return (b + u128(u64(b) * u64(-r)) * mod) >> 64;
    }
    u64 get() const {
        u64 ret = reduce(a);
        return ret >= mod ? ret - mod : ret;
    }
    m64 &operator*=(const m64 &b) {
        a = reduce(u128(a) * b.a);
        return *this;
    }
    m64 operator*(const m64 &b) const { return m64(*this) *= b; }
    bool operator==(const m64 &b) const {
        return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
    }
    bool operator!=(const m64 &b) const {
        return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
    }
    m64 pow(u128 n) const {
        m64 ret(1), mul(*this);
        while (n > 0) {
        if (n & 1) ret *= mul;
        mul *= mul;
        n >>= 1;
        }
        return ret;
    }
};
typename m64::u64 m64::mod, m64::r, m64::n2;

bool Miller(ll n){
    if(n<2 or (n&1)==0)return (n==2);
    m64::set_mod(n);
    ll d=n-1; while((d&1)==0)d>>=1;
    vector<ll> seeds;
    if(n<(1<<30))seeds={2, 7, 61};
    else seeds={2, 325, 9375, 28178, 450775, 9780504};
    for(auto& x:seeds){
        if(n<=x)break;
        ll t=d;
        m64 y=m64(x).pow(t);
        while(t!=n-1 and y!=1 and y!=n-1){
            y*=y;
            t<<=1;
        }
        if(y!=n-1 and (t&1)==0)return 0;
    } return 1;
}

/**
 * @brief Miller-Rabin
 */
#line 2 "library/Utility/random.hpp"

mt19937_64 _randgen(chrono::steady_clock::now().time_since_epoch().count());
struct Random{
    using u64=unsigned long long;
    Random(){}
    u64 get(){
        return _randgen();
    }
    template<typename T>T get(T L){
        return get()%(L+1);
    }
    template<typename T>T get(T L,T R){
        return get(R-L)+L;
    }
    double uniform(){
        return double(get(1000000000))/1000000000;
    }
    string str(int n){
        string ret;
        rep(i,0,n)ret+=get('a','z');
        return ret;
    }
    template<typename Iter>void shuffle(Iter first,Iter last){
        if(first==last)return;
        int len=1;
        for(auto it=first+1;it!=last;it++){
            len++;
            int j=get(0,len-1);
            if(j!=len-1)iter_swap(it,first+j);
        }
    }
    template<typename T>vector<T> select(int n,T L,T R){
        set<T> ret;
        while(ret.size()<n)ret.insert(get(L,R));
        return {ALL(ret)};
    }
};

/**
 * @brief Random
 */
#line 4 "library/Math/pollard.hpp"

Random genPollard;
vector<ll> Pollard(ll n){
    if(n<=1)return {};
    if(Miller(n))return {n};
    if((n&1)==0){
        vector<ll> v=Pollard(n>>1); v.push_back(2);
        return v;
    }
    for(ll x=2,y=2,d;;){
        ll c=genPollard.get(2LL,n-1);
        do{
            x=(__int128_t(x)*x+c)%n;
            y=(__int128_t(y)*y+c)%n;
            y=(__int128_t(y)*y+c)%n;
            d=__gcd(x-y+n,n);
        }while(d==1);
        if(d<n){
            vector<ll> lb=Pollard(d),rb=Pollard(n/d);
            lb.insert(lb.end(),ALL(rb)); return lb;
        }
    }
}

/**
 * @brief Pollard-Rho
 */
#line 2 "library/Convolution/bitwise.hpp"

namespace Bitwise{
    template<typename T>void zeta(vector<T>& a){
        int n=__lg(a.size());
        rep(k,0,n)rep(mask,0,1<<n){
            if(mask>>k&1)a[mask]+=a[mask^(1<<k)];
        }
    }
    template<typename T>void mobius(vector<T>& a){
        int n=__lg(a.size());
        rep(k,0,n)rep(mask,0,1<<n){
            if(mask>>k&1)a[mask]-=a[mask^(1<<k)];
        }
    }
    template<typename T>void fwt(vector<T>& a){
        int n=__lg(a.size());
        rep(k,0,n)rep(mask,0,1<<n){
            if(!(mask>>k&1)){
                T x=a[mask],y=a[mask|(1<<k)];
                a[mask]=x+y,a[mask|(1<<k)]=x-y;
            }
        }
    }
};

/**
 * @brief Bitwise Convolution
 * @docs docs/bitwise.md
 */
#line 9 "sol.cpp"

ll m;
map<ll,int> pe;


FastIO io;
void solve(int _rot){
    // io.write<false>("Case #"+to_string(_rot)+": ");
    int n,B,C,D;
    io.read(n,B,C,D);
    vector<Fp> w(n);
    w[0]=B;
    rep(i,1,n)w[i]=w[i-1]*C+D;
    vector<int> mask(n); // -1:not use
    rep(i,0,n){
        ll x;
        io.read(x);
        if(m%x!=0){mask[i]=-1; continue;}
        int j=0;
        for(auto& [p,e]:pe){
            int cnt=0;
            while(x%p==0){
                cnt++;
                x/=p;
            }
            if(cnt>e){mask[i]=-1; break;}
            else if(cnt==e)mask[i]|=(1<<j);
            j++;
        }
    }

    int sz=pe.size();
    Fp zero=1;
    rep(i,0,n)if(mask[i]==0)zero*=(w[i]+1);

    vector<Fp> base(1<<sz,1);
    rep(i,0,n)if(mask[i]>0){
        // vector<Fp> ref(1<<sz);
        // ref[0]=1;
        // ref[mask[i]]=w[i];
        // rep(j,0,1<<sz)cerr<<ref[j].v<<' ';
        // cerr<<'\n';
        // Bitwise::zeta(ref);
        // rep(j,0,1<<sz)cerr<<ref[j].v<<' ';
        // cerr<<'\n';
        // rep(j,0,1<<sz)base[j]*=ref[j];
        base[mask[i]]*=w[i]+1;
    }
    rep(k,0,sz)rep(mask,0,1<<sz){
        if(mask>>k&1)base[mask]*=base[mask^(1<<k)];
    }
    Bitwise::mobius(base);
    Fp ret=base[(1<<sz)-1]*zero;
    if(m==1)ret-=1;
    io.write(ret.v);
}

int main(){
    int t;
    io.read(t,m);
    auto ps=Pollard(m);
    for(auto& p:ps)pe[p]++;

    rep(rot,0,t)solve(rot+1);
    return 0;
}

yukicoder

結果

テストケース

ソースコード