ライブラリのバグを修正できました。
http://yukicoder.me/problems/184
問題
T個のクエリが与えられる。
各クエリは計算種別(C,P,Hのいずれか)と2値N,Kからなる。
それぞれの種別に対し
- 種別がC: を答えよ
- 種別がP: を答えよ
- 種別がH: を答えよ
なお、N,Kは0以上10^6以下である。
解法
CとPの計算方法を考えると、なので階乗や階乗の逆数を事前に10^6まで求めておくと、各クエリはO(1)で処理できる。
Hについては基本的にである。
参考:組合せ (数学) - Wikipedia
しかしN==K==0の時だけはこの式ではとなりCombinationのルーチン次第ではうまく計算できない。
この場合だけ特別に処理してやる必要がある。
自分もこれでWAを連発した。
ll mo=1000000007; const int NUM_=2000003; ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; void init() { int i; inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; } ll combi(ll N_, ll C_) { if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } ll perm(ll N_, ll C_) { if(C_<0 || C_>N_) return 0; return fact[N_]*factr[N_-C_]%mo; } ll hcomb(int P_,int Q_) { if(P_==0 && Q_==0) return 1; return combi(P_+Q_-1,Q_); } int T; char hoge[1010]; void solve() { int i,j,k,l,r,x,y; string s; init(); scanf("%d",&T); FOR(i,T) { scanf("%1s(%d,%d)",hoge,&x,&y); ll ret=0; if(hoge[0]=='C') ret=combi(x,y); else if(hoge[0]=='P') ret=per(x,y); else if(hoge[0]=='H') ret=hcomb(x,y); cout<<ret<<endl; } }
まとめ
ライブラリのバグ修正ゲーになってしまった。