結果
問題 | No.389 ロジックパズルの組み合わせ |
ユーザー |
![]() |
提出日時 | 2016-07-08 23:37:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,591 bytes |
コンパイル時間 | 619 ms |
コンパイル使用メモリ | 66,152 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 07:22:12 |
合計ジャッジ時間 | 3,697 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 99 |
ソースコード
#include <iostream> using namespace std; int p=1000000007; /* int mod_comb(int n,int k,int p){ if(n<0||k<0||n<k)return 0; if(k==0)return 1; return (mod_comb(n-1,k,p)+mod_comb(n-1,k-1,p))%p; }*/ int extgcd(int a, int b, int&x, int&y){ int d=a; if(b!=0){ d=extgcd(b,a%b,y,x); y-=(a/b)*x; }else{ x=1;y=0; } return d; } int mod_inverse(int a, int m){ int x, y; extgcd(a,m,x,y); return (m+x%m)%m; } int fact(int n, int p){ long long int res=1; while(n){ res*=n; if(res>p)res%=p; if(res==0)return 0; n--; } return (int)res; } int mod_fact(int n,int p,int &e){ e=0; if(n==0)return 1; long long int res=mod_fact(n/p,p,e); e+=n/p; if(n/p%2!=0) return res*(p-fact(n%p,p))%p; return (int)(res*fact(n%p,p)%p); } int mod_comb(int n, int k,int p){ if(n<0||k<0||n<k)return 0; int e1,e2,e3; long long int a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3); if(e1>e2+e3)return 0; return (a1*mod_inverse(a2*a3%p,p))%p; } int main(){ int M; cin>>M; int count=0, black=0, part; while(cin>>part){ count++; black+=part; } if(!black){ cout<<1<<endl; return 0; } if(M<black+count-1)cout<<"NA"<<endl; else //M-black-(count-1)個のwhileをcount+1個に分割する。(M-black+count)C(count) //cout<<mod_comb(5,3,p)<<endl; //cout<<M-black+1<<' '<<count<<endl; //cout<<fact(M-black+1,p)<<endl; cout<<mod_comb(M-black+1,count,p)<<endl; return 0; }