結果

問題 No.1857 Gacha Addiction
ユーザー ytqm3ytqm3
提出日時 2022-02-25 22:09:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 371 ms / 6,000 ms
コード長 6,042 bytes
コンパイル時間 5,912 ms
コンパイル使用メモリ 273,388 KB
実行使用メモリ 83,656 KB
最終ジャッジ日時 2023-09-16 17:08:28
合計ジャッジ時間 18,359 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
26,336 KB
testcase_01 AC 36 ms
26,564 KB
testcase_02 AC 36 ms
26,512 KB
testcase_03 AC 38 ms
26,460 KB
testcase_04 AC 41 ms
27,484 KB
testcase_05 AC 40 ms
27,772 KB
testcase_06 AC 42 ms
27,516 KB
testcase_07 AC 41 ms
27,600 KB
testcase_08 AC 40 ms
27,496 KB
testcase_09 AC 122 ms
42,660 KB
testcase_10 AC 134 ms
42,724 KB
testcase_11 AC 131 ms
42,848 KB
testcase_12 AC 127 ms
42,700 KB
testcase_13 AC 126 ms
42,676 KB
testcase_14 AC 358 ms
83,500 KB
testcase_15 AC 356 ms
83,372 KB
testcase_16 AC 360 ms
83,344 KB
testcase_17 AC 362 ms
83,384 KB
testcase_18 AC 363 ms
83,404 KB
testcase_19 AC 366 ms
83,348 KB
testcase_20 AC 361 ms
83,348 KB
testcase_21 AC 365 ms
83,440 KB
testcase_22 AC 360 ms
83,460 KB
testcase_23 AC 361 ms
83,440 KB
testcase_24 AC 362 ms
83,432 KB
testcase_25 AC 362 ms
83,500 KB
testcase_26 AC 360 ms
83,392 KB
testcase_27 AC 360 ms
83,344 KB
testcase_28 AC 354 ms
83,468 KB
testcase_29 AC 368 ms
83,408 KB
testcase_30 AC 356 ms
83,348 KB
testcase_31 AC 368 ms
83,512 KB
testcase_32 AC 358 ms
83,396 KB
testcase_33 AC 371 ms
83,656 KB
testcase_34 AC 365 ms
83,348 KB
testcase_35 AC 358 ms
83,428 KB
testcase_36 AC 356 ms
83,376 KB
testcase_37 AC 355 ms
83,400 KB
testcase_38 AC 365 ms
83,504 KB
testcase_39 AC 132 ms
43,832 KB
testcase_40 AC 137 ms
44,540 KB
testcase_41 AC 181 ms
54,612 KB
testcase_42 AC 66 ms
33,280 KB
testcase_43 AC 327 ms
81,244 KB
testcase_44 AC 346 ms
83,444 KB
testcase_45 AC 37 ms
26,360 KB
testcase_46 AC 37 ms
26,404 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
typedef uint64_t u64;
typedef int64_t i64;
using namespace std;
template<u64 mod> using modint=atcoder::static_modint<mod>;

template<typename T> struct comb{
  vector<T> dat,idat;
  comb(int mx=3000000):dat(mx+1,1),idat(mx+1,1){
    for(int i=1;i<=mx;++i){
      dat[i]=dat[i-1]*i;
    }
    idat[mx]/=dat[mx];
    for(int i=mx;i>0;--i){
      idat[i-1]=idat[i]*i;
    }
  }
  T operator()(int n,int k){
    if(n<0||k<0||n<k){
      return 0;
    }
    return dat[n]*idat[k]*idat[n-k];
  }
};

template<u64 mod> struct FPS{
  typedef modint<mod> mint;
  vector<mint> val;
  FPS():val({0}){}
  FPS(mint t):val({t}){}
  FPS(int siz):val(max(1,siz)){}
  FPS(initializer_list<modint<mod>> init):val(init){}
  FPS(vector<mint> init):val(init){}
  mint &operator[](int i){
    return val[i];
  }
  int size(){
    return val.size();
  }
  void resize(int siz){
    val.resize(siz);
  }
  FPS& resize_(int siz){
    auto tmp=val;
    tmp.resize(siz);
    return (*this)=tmp;
  }
  FPS operator-(){
    for(mint& v:val){
      v=mint(0)-v;
    }
    return (*this);
  }
  FPS& operator+=(mint rhs){
    val[0]+=rhs;
    return (*this);
  }
  FPS& operator-=(mint rhs){
    val[0]-=rhs;
    return (*this);
  }
  FPS& operator*=(mint rhs){
    for(auto& v:val){
      v*=rhs;
    }
    return (*this);
  }
  FPS& operator/=(mint rhs){
    for(auto& v:val){
      v/=rhs;
    }
    return (*this);
  }
  FPS operator+(mint rhs){
    return FPS(*this)+=rhs;
  }
  FPS operator-(mint rhs){
    return FPS(*this)-=rhs;
  }
  FPS operator*(mint rhs){
    return FPS(*this)*=rhs;
  }
  FPS operator/(mint rhs){
    return FPS(*this)/=rhs;
  }
  FPS& operator+=(FPS rhs){
    resize(max(this->size(),rhs.size()));
    for(int i=0;i<int(rhs.size());++i){
      (*this)[i]+=rhs[i];
    }
    return (*this);
  }
  FPS& operator-=(FPS rhs){
    resize(max(this->size(),rhs.size()));
    for(int i=0;i<int(rhs.size());++i){
      (*this)[i]-=rhs[i];
    }
    return (*this);
  }
  FPS& operator*=(FPS rhs){
    val=atcoder::convolution(val,rhs.val);
    return (*this);
  }
  FPS& operator/=(FPS rhs){
    return (*this)*=rhs.inv();
  }
  FPS& operator>>=(int k){
    if(int(val.size())<=k){
      return (*this)={0};
    }
    FPS res=val;
    res.val.erase(res.val.begin(),res.val.begin()+k);
    return (*this)=res;
  }
  FPS& operator<<=(int k){
    FPS res=val;
    res.val.insert(res.val.begin(),k,mint(0));
    return (*this)=res;
  }
  FPS operator+(FPS rhs){
    return FPS(*this)+=rhs;
  }
  FPS operator-(FPS rhs){
    return FPS(*this)-=rhs;
  }
  FPS operator*(FPS rhs){
    return FPS(*this)*=rhs;
  }
  FPS operator/(FPS rhs){
    return FPS(*this)/=rhs;
  }
  FPS operator<<(int k){
    return FPS(*this)<<=k;
  }
  FPS operator>>(int k){
    return FPS(*this)>>=k;
  }
  FPS shrink(){
    for(int i=val.size()-1;i>0;--i){
      if(val[i]==0){
        val.pop_back();
      }
      else{
        break;
      }
    }
    return (*this);
  }
  FPS diff_(){
    if(val.size()==1){
      return (*this)={0};
    }
    FPS f(val.size()-1);
    for(size_t i=1;i<val.size();++i){
      f[i-1]=val[i]*i;
    }
    return f;
  }
  FPS integral_(){
    FPS f(val.size()+1);
    for(size_t i=0;i<val.size();++i){
      f[i+1]=val[i]/(i+1);
    }
    return f;
  }
  FPS inv_(int mx=-1){
    if(mx==-1){
      mx=val.size();
    }
    if(val[0]==0){
      assert(0);
    }
    FPS g({mint(1)/val[0]});
    int now=1;
    while(now<mx){
      now<<=1;
      FPS t=(*this);
      t.resize(now);
      t*=g;
      t=-t+mint(2);
      g*=t;
      g.resize(now);
    }
    g.resize(mx);
    return g;
  }
  FPS exp_(int mx=-1){
    if(mx==-1){
      mx=val.size();
    }
    if(val[0]!=0){
      assert(0);
    }
    FPS g(mint(1));
    int now=1;
    while(now<mx){
      now<<=1;
      FPS t=(*this);
      t.resize(now);
      g*=t-g.log_(now)+mint(1);
      g.resize(now);
    }
    g.resize(mx);
    return g;
  }
  FPS log_(int mx=-1){
    if(mx==-1){
      mx=val.size();
    }
    if(val[0]!=1){
      assert(0);
    }
    auto f=(*this);
    f.resize(mx);
    return (f.diff_()/f).integral_().resize_(mx);
  }
  FPS pow_(i64 k,int mx=-1){
    if(mx==-1){
      mx=val.size();
    }
    i64 t=0;
    for(auto v:val){
      if(v==0){
        t++;
      }
      else{
        break;
      }
    }
    auto f=(*this)>>t;
    if(f[0]==0){
      f={0},f.resize(mx);
      return f;
    }
    mint c=f[0];
    f/=c;
    (f.log(mx)*=mint(k)).exp(mx)*=c.pow(k);
    if(t*k<=mx){
      f<<=t*k;
      f.resize(mx);
      return f;
    }
    else{
      f={0},f.resize(mx);
      return f;
    }
  }
  FPS& diff(){
    return (*this)=diff_();
  }
  FPS& integral(){
    return (*this)=integral_();
  }
  FPS& inv(int mx=-1){
    return (*this)=inv_(mx);
  }
  FPS& exp(int mx=-1){
    return (*this)=exp_(mx);
  }
  FPS& log(int mx=-1){
    return (*this)=log_(mx);
  }
  FPS& pow(i64 k,int mx=-1){
    return (*this)=pow_(k,mx);
  }
  void taylor_shift(mint c){
    comb<mint> C(val.size());
    vector<mint> g(val.size());
    mint now=1;
    for(size_t i=0;i<val.size();++i){
      val[i]*=C.dat[i];
      g[i]=now*C.idat[i];
      now*=c;
    }
    reverse(val.begin(),val.end());
    g=atcoder::convolution(val,g);
    g.resize(val.size());
    reverse(g.begin(),g.end());
    for(size_t i=0;i<val.size();++i){
      g[i]*=C.idat[i];
    }
    val=g;
  }
};

template<u64 mod> FPS<mod> product(vector<FPS<mod>> a){
  int siz=1;
  while(siz<int(a.size())){
    siz<<=1;
  }
  vector<FPS<mod>> res(siz*2-1,{1});
  for(int i=0;i<int(a.size());++i){
    res[i+siz-1]=a[i];
  }
  for(int i=siz-2;i>=0;--i){
    res[i]=res[2*i+1]*res[2*i+2];
  }
  return res[0];
}

int main(){
  typedef modint<998244353> mint;
  constexpr u64 mod=998244353;
  int N,S;
  cin>>N>>S;
  vector<FPS<mod>> f(N);
  comb<mint> C;
  mint invS=mint(1)/S;
  for(int i=0;i<N;++i){
    int p;
    cin>>p;
    f[i]={1,invS*p};
  }
  auto g=product(f);
  mint ans=0;
  for(int i=0;i<=N;++i){
    ans+=C.dat[i]*g[i];
  }
  cout<<ans.val()<<endl;
}
0