結果
問題 | No.498 ワープクリスタル (給料日編) |
ユーザー | conf |
提出日時 | 2017-03-24 23:23:38 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 2,262 bytes |
コンパイル時間 | 588 ms |
コンパイル使用メモリ | 66,892 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-20 03:51:14 |
合計ジャッジ時間 | 1,883 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
4,380 KB |
testcase_01 | AC | 4 ms
4,380 KB |
testcase_02 | AC | 4 ms
4,376 KB |
testcase_03 | AC | 4 ms
4,376 KB |
testcase_04 | AC | 14 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 14 ms
4,376 KB |
testcase_07 | AC | 16 ms
4,384 KB |
testcase_08 | AC | 14 ms
4,376 KB |
testcase_09 | AC | 12 ms
4,376 KB |
testcase_10 | AC | 4 ms
4,380 KB |
testcase_11 | AC | 5 ms
4,376 KB |
testcase_12 | AC | 3 ms
4,384 KB |
testcase_13 | AC | 4 ms
4,376 KB |
testcase_14 | AC | 4 ms
4,380 KB |
testcase_15 | AC | 4 ms
4,376 KB |
testcase_16 | AC | 4 ms
4,380 KB |
testcase_17 | AC | 4 ms
4,380 KB |
testcase_18 | AC | 14 ms
4,376 KB |
testcase_19 | AC | 14 ms
4,376 KB |
testcase_20 | AC | 14 ms
4,376 KB |
testcase_21 | AC | 14 ms
4,376 KB |
testcase_22 | AC | 14 ms
4,376 KB |
testcase_23 | AC | 14 ms
4,380 KB |
testcase_24 | AC | 14 ms
4,380 KB |
ソースコード
#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; }