結果
問題 | No.498 ワープクリスタル (給料日編) |
ユーザー |
|
提出日時 | 2020-02-12 00:07:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 800 bytes |
コンパイル時間 | 819 ms |
コンパイル使用メモリ | 70,328 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 12:54:54 |
合計ジャッジ時間 | 2,220 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
コンパイルメッセージ
main.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 37 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>using namespace std;long mod=1e9+7;long F[99],I[99];long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}int gx,gy;int x[5],y[5],n[5];int K;vector<int>tmp;long dfs(int X,int Y,int id){if(id==5){if(X==gx&&Y==gy){int s=0;for(int k:tmp)s+=k;long ret=F[s];for(int k:tmp)ret=ret*I[k]%mod;return ret;}else return 0;}long ret=0;tmp.push_back(0);for(int k=0;k<=n[id];k++){ret+=dfs(X,Y,id+1);tmp.back()++;X+=x[id];Y+=y[id];}tmp.pop_back();return ret%mod;}main(){F[0]=1;for(int i=1;i<99;i++)F[i]=F[i-1]*i%mod;I[98]=power(F[98],mod-2);for(int i=98;i--;)I[i]=I[i+1]*(i+1)%mod;cin>>gx>>gy>>K;for(int i=0;i<K;i++){cin>>x[i]>>y[i]>>n[i];}cout<<dfs(0,0,0)<<endl;}