結果

問題 No.117 組み合わせの数
コンテスト
ユーザー 夕叢霧香(ゆうむらきりか)
提出日時 2018-01-08 13:40:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 298 ms / 5,000 ms
コード長 1,069 bytes
コンパイル時間 726 ms
コンパイル使用メモリ 78,188 KB
最終ジャッジ日時 2025-01-05 07:12:44
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<iostream>
#include<sstream>
#include<vector>
using namespace std;
#define int long long
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

#define mod 1000000007LL

int fact[2000100];

int powmod(int x,int e){
  int prod = 1;
  for (int i = 63; i >= 0; --i) {
    prod = (prod * prod) % mod;
    if ((e & 1L << i) != 0) {
      prod = (prod * x) % mod;
    }
  }
  return prod;
}

int c(int x,int y){
  if(x<y||y<0)return 0;
  return fact[x]*powmod(fact[x-y]*fact[y]%mod,mod-2)%mod;
}

int h(int x,int y){
  if(x==0)return y==0?1:0;
  return c(x+y-1,y);
}

int p(int x,int y){
  if(x<y)return 0;
  return fact[x]*powmod(fact[x-y],mod-2)%mod;
}

signed main(){
  fact[0]=1;
  rep(i,2000099){
    fact[i+1]=fact[i]*(i+1)%mod;
  }
  int n;
  cin>>n;
  rep(i,n){
    string s;
    cin>>s;
    char ch=s[0];
    int n,k;
    stringstream ss(s.substr(2));
    ss>>n;
    ss.ignore();
    ss>>k;
    if(ch=='C')cout<<c(n,k);
    else if(ch=='P')cout<<p(n,k);
    else cout<<h(n,k);
    cout<<"\n";
  }
}
0