結果

問題 No.2313 Product of Subsequence (hard)
ユーザー driz
提出日時 2026-01-27 15:22:51
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 417 ms / 4,000 ms
コード長 4,602 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,835 ms
コンパイル使用メモリ 235,704 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-27 15:23:01
合計ジャッジ時間 8,735 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#define ALL(v) v.begin(),v.end()
#define For(i,_) for(int i=0,i##end=_;i<i##end;++i) // [0,_)
#define FOR(i,_,__) for(int i=_,i##end=__;i<i##end;++i) // [_,__)
#define Rep(i,_) for(int i=(_)-1;i>=0;--i) // [0,_)
#define REP(i,_,__) for(int i=(__)-1,i##end=_;i>=i##end;--i) // [_,__)
typedef long long ll;
typedef unsigned long long ull;
#define V vector
#define pb push_back
#define pf push_front
#define qb pop_back
#define qf pop_front
#define eb emplace_back
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define fi first
#define se second
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},inf=0x3f3f3f3f,mod=998244353;
const ll infl=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
namespace{int init=[](){return cin.tie(nullptr)->sync_with_stdio(false),0;}();}
template<int p>
struct modint{
    int val;
    inline modint(int v=0):val(v){}
    inline modint& operator=(int v){val=v;return *this;}
    inline modint& operator+=(const modint&k){val=val+k.val>=p?val+k.val-p:val+k.val;return *this;}
    inline modint& operator-=(const modint&k){val=val-k.val<0?val-k.val+p:val-k.val;return *this;}
    inline modint& operator*=(const modint&k){val=int(1ll*val*k.val%p);return *this;}
    inline modint& operator^=(int k){modint r(1),b=*this;for(;k;k>>=1,b*=b)if(k&1)r*=b;val=r.val;return *this;}
    inline modint& operator/=(modint k){return *this*=(k^=p-2);}
    inline modint& operator+=(int k){val=val+k>=p?val+k-p:val+k;return *this;}
    inline modint& operator-=(int k){val=val<k?val-k+p:val-k;return *this;}
    inline modint& operator*=(int k){val=int(1ll*val*k%p);return *this;}
    inline modint& operator/=(int k){return *this*=((modint(k))^=p-2);}
    template<class T>friend modint operator+(modint a,T b){return a+=b;}
    template<class T>friend modint operator-(modint a,T b){return a-=b;}
    template<class T>friend modint operator*(modint a,T b){return a*=b;}
    template<class T>friend modint operator/(modint a,T b){return a/=b;}
    friend modint operator^(modint a,int b){return a^=b;}
    friend bool operator==(modint a,int b){return a.val==b;}
    friend bool operator!=(modint a,int b){return a.val!=b;}
    inline bool operator!()const{return !val;}
    inline modint operator-()const{return val?modint(p-val):modint(0);}
    inline modint operator++(int){modint t=*this;*this+=1;return t;}
    inline modint& operator++(){return *this+=1;}
    inline modint operator--(int){modint t=*this;*this-=1;return t;}
    inline modint& operator--(){return *this-=1;}
};
using mi=modint<mod>;
struct custom_hash{
    static uint64_t splitmix64(uint64_t x){
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30))*0xbf58476d1ce4e5b9;
        x=(x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
    }
    size_t operator()(uint64_t x)const{
        static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x+FIXED_RANDOM);
    }
};
struct comb_table{
    int n;
    V<mi>fac,ifac;
    inline comb_table(int n=0):n(n),fac(n+1),ifac(n+1){init();}
    inline void init(){
        fac[0]=1;
        FOR(i,1,n+1)fac[i]=fac[i-1]*i;
        ifac[n]=1/fac[n];
        Rep(i,n)ifac[i]=ifac[i+1]*(i+1);
    }
    inline mi C(int x,int y){return x<y||y<0?0:fac[x]*ifac[y]*ifac[x-y];}
    inline mi inv(int k){return ifac[k]*fac[k-1];}
    inline mi catalan(int n,int m=1,int p=2){return C(n*p+m,n)*m*inv(n*p+m);}
};
int main(){
    int t_case=1;
    //scanf("%d",&t_case);
    while(t_case--){
        int k,n;
        scanf("%d%d",&n,&k);
        V<mi>pw2(n+1);
        pw2[0]=1;
        FOR(i,1,n+1)pw2[i]=pw2[i-1]+pw2[i-1];
        unordered_map<int,int,custom_hash>cnt;
        comb_table ct(n);
        while(n--){
            ll x;
            scanf("%lld",&x);
            ++cnt[gcd<ll>(x,k)];
        }
        unordered_map<int,mi,custom_hash>f,g;
        f[1]=1;
        for(const auto &[i,j]:cnt){
            int l=1,pw=1,tmp=k;
            while(l<j&&gcd(i,tmp/gcd(tmp,i))>1)++l,tmp/=gcd(tmp,i);
            g=f;
            mi tot=pw2[j]-1;
            FOR(m,1,l+1){
                mi coef=m<l?ct.C(j,m):tot;
                pw=gcd<ll>(1ll*pw*i,k);
                for(const auto &[o,p]:f)g[gcd<ll>(1ll*pw*o,k)]+=coef*p;
                tot-=coef;
            }
            f.swap(g);
        }
        printf("%d\n",f[k]-(k==1));
    }
    return 0;
}
0