結果

問題 No.117 組み合わせの数
ユーザー cureskolcureskol
提出日時 2022-12-11 19:36:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 98 ms / 5,000 ms
コード長 3,286 bytes
コンパイル時間 2,325 ms
コンパイル使用メモリ 207,684 KB
実行使用メモリ 44,268 KB
最終ジャッジ日時 2024-10-15 15:40:29
合計ジャッジ時間 2,828 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 98 ms
44,268 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "test/yukicoder/117.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/117"
#include <bits/stdc++.h>
using namespace std;

#line 1 "mod/Modint.cpp"
template<typename T,T MOD=998244353>
struct Mint{
  inline static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0)v+=MOD;}
  
  static Mint raw(int v){
    Mint x;
    x.v=v;
    return x;
  }

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1)res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator+() const{return *this;}
  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }

  friend ostream& operator<<(ostream&os,const Mint &m){os<<m.v;return os;}
  friend istream& operator>>(istream&is,Mint &m){is>>m.v;m.v%=MOD;if(m.v<0)m.v+=MOD;return is;}
};
#line 1 "mod/MintUtility.cpp"
template<typename MINT>
class MintUtility{
  vector<MINT> fact_={MINT::raw(1)};
  vector<MINT> inv_fact_{MINT::raw(1)};
  int S=1;//今のサイズ

  void extend(const int n){
    if(n<S)return;
    const int preS=S;
    do{S<<=1;}while(S<=n);

    fact_.resize(S);
    for(int i=preS;i<S;i++)fact_[i]=fact_[i-1]*MINT::raw(i);

    inv_fact_.resize(S);
    inv_fact_.back()=fact_.back().inv();
    for(int i=S-1;i>preS;i--)inv_fact_[i-1]=inv_fact_[i]*MINT::raw(i);
  }
public:
  MINT fact(const int n){
    assert(n>=0);
    extend(n);
    return fact_[n];
  }
  MINT inv_fact(const int n){
    assert(n>=0);
    extend(n);
    return inv_fact_[n];
  }
  MINT nCk(const int n,const int k){
    if(k<0||n<k)return MINT::raw(0);
    extend(n);
    return fact_[n] * inv_fact_[k] * inv_fact_[n - k];
  }
  MINT nPk(const int n,const int k){
    if(k<0||n<k)return MINT::raw(0);
    extend(n);
    return fact_[n] * inv_fact_[n-k];
  }
  MINT nHk(const int n,const int k){
    return (n==0 and k==0?1:nCk(n+k-1,k));
  }
};
#line 7 "test/yukicoder/117.test.cpp"
int digit(char c){ return (c>='0' and c<='9' ? c-'0' : -1);}

using mint=Mint<long long,1000'000'007>;
MintUtility<mint> M;

mint solve(){
  string s;cin>>s;
  int comma=0;
  while(s[comma]!=',')comma++;
  int n=stoi(s.substr(2,comma-1));
  int k=stoi(s.substr(comma+1,s.size()-comma-1));
  if(s[0]=='C')return M.nCk(n,k);
  if(s[0]=='P')return M.nPk(n,k);
  return M.nHk(n,k);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int testsize;cin>>testsize;
  while(testsize--)cout<<solve()<<'\n';
}
0