結果
問題 | No.117 組み合わせの数 |
ユーザー | fiord |
提出日時 | 2015-08-16 00:42:42 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 141 ms / 5,000 ms |
コード長 | 771 bytes |
コンパイル時間 | 2,071 ms |
コンパイル使用メモリ | 143,788 KB |
実行使用メモリ | 81,612 KB |
最終ジャッジ日時 | 2023-09-25 12:14:57 |
合計ジャッジ時間 | 1,991 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define E 1000000007 ll res[10000000]; ll calc(ll a,int b=E-2){ ll ans=1; while(b){ if(b&1) ans=(ans*a)%E; a=(a*a)%E; b>>=1; } return ans; } ll ncm(ll n,ll m){ return (res[n]*calc(res[m])%E)*calc(res[n-m])%E; } int main(){ res[0]=res[1]=1; for(int i=2;i<10000000;i++) res[i]=i*res[i-1]%E; int t; scanf("%d",&t); while(t--){ int n,k; char s; scanf(" %c(%d,%d)",&s,&n,&k); if(n<k&&s!='H'){ printf("0\n"); continue; } switch(s){ case 'C': printf("%lld\n",ncm(n,k)); break; case 'P': printf("%lld\n",res[n]*calc(res[n-k])%E); break; case 'H': if(n+k==0) printf("1\n"); else printf("%lld\n",ncm(n+k-1,k)); break; } } return 0; }