結果
問題 | No.498 ワープクリスタル (給料日編) |
ユーザー |
![]() |
提出日時 | 2017-03-24 23:23:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 2,262 bytes |
コンパイル時間 | 598 ms |
コンパイル使用メモリ | 66,944 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-06 00:08:08 |
合計ジャッジ時間 | 1,531 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <iostream> using namespace std; int64_t p=1000000007; int64_t extgcd(int64_t a, int64_t b, int64_t&x, int64_t&y){ int64_t d=a; if(b!=0){ d=extgcd(b,a%b,y,x); y-=(a/b)*x; }else{ x=1;y=0; } return d; } int64_t mod_pow(int64_t a, int64_t e, int64_t p){ int64_t res = 1; for(;e>0;e>>=1){ if(e&1)res=(res*a)%p; a=(a*a)%p; } return res; } int64_t mod_inverse(int64_t a, int64_t m){ int64_t x, y; extgcd(a,m,x,y); return (m+x%m)%m; } int64_t fact(int64_t n, int64_t p){ static int64_t F[100001]; if(F[n]) return F[n]; else{ F[0]=1; for(int64_t i=1;i<=100000;i++){ F[i]=i*F[i-1]%p; } return F[n]; } int64_t res=1; while(n){ res*=n; if(res>p)res%=p; if(res==0)return 0; n--; } return res; } int64_t mod_fact(int64_t n,int64_t p,int64_t &e){ static int64_t F[100001]; if(F[n]) return F[n]; e=0; if(n==0)return 1; int64_t res=mod_fact(n/p,p,e); e+=n/p; if(n/p%2!=0) return F[n]=res*(p-fact(n%p,p))%p; return F[n]=res*fact(n%p,p)%p; } int64_t mod_comb(int64_t n, int64_t k,int64_t p){ if(n<0||k<0||n<k)return 0; int64_t e1,e2,e3; int64_t 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; return a1*mod_pow(a2*a3%p,p-2,p)%p; } int main(){ int X[5],Y[5],N[5],n[5]; fill(N,N+5,0); int Gx,Gy,K; cin>>Gx>>Gy>>K; for(int i=0;i<K;i++){ cin>>X[i]>>Y[i]>>N[i]; } int64_t ans = 0; for(n[0]=0;n[0]<=N[0];n[0]++) for(n[1]=0;n[1]<=N[1];n[1]++) for(n[2]=0;n[2]<=N[2];n[2]++) for(n[3]=0;n[3]<=N[3];n[3]++) for(n[4]=0;n[4]<=N[4];n[4]++){ int XX=0,YY=0,NN=0; for(int i=0;i<K;i++){ NN+=n[i]; XX+=n[i]*X[i]; YY+=n[i]*Y[i]; } if(XX==Gx&&YY==Gy){ int64_t C=fact(NN,p); for(int i=0;i<K;i++){ if(n[i]){ C=(C*mod_inverse(fact(n[i],p),p))%p; } } ans+=C; ans%=p; } } cout<<ans<<endl; return 0; }