結果

問題 No.117 組み合わせの数
ユーザー cureskolcureskol
提出日時 2022-12-11 19:36:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 107 ms / 5,000 ms
コード長 3,286 bytes
コンパイル時間 2,277 ms
コンパイル使用メモリ 198,692 KB
最終ジャッジ日時 2025-02-09 09:45:44
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0