結果
問題 | No.117 組み合わせの数 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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';}