結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー ixmelixmel
提出日時 2017-03-24 23:18:41
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 1,704 bytes
コンパイル時間 800 ms
コンパイル使用メモリ 90,396 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 00:02:02
合計ジャッジ時間 1,584 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e8;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
ll out;
ll x,y,n;
vvi in;
#define MOD 1000000007
// a^b mod MOD
ll powmod(ll a,ll b){
	ll out=1;
	ll p=a%MOD;
	while(b){
		if(b&1)out=out*p%MOD;
		p=p*p%MOD;
		b>>=1;
	}
	return out;
}
#define M 1000
vector<ll> fact;
void init(){
	fact=vector<ll>(M);
	fact[0]=fact[1]=1;
	loop(i,2,M)fact[i]=fact[i-1]*i%MOD;
}
// nCr
ll nCr(ll n,ll r){
	ll out=fact[n]*powmod(fact[r]*fact[n-r]%MOD,MOD-2)%MOD;
	return out;
}	
vi co;
void f(int a,int nx,int ny){
	if(a==n){
		if(nx!=x||ny!=y)return;
		ll sum=0;
		rep(i,n)sum+=co[i];
		ll ot=1;
		rep(i,n){
//			cout<<sum<<" "<<co[i]<<endl;
			(ot*=nCr(sum,co[i]))%=MOD;
			sum-=co[i];
		}
		(out+=ot)%=MOD;
		return;
	}
	rep(i,in[a][2]+1){
		co[a]=i;
		f(a+1,nx+i*in[a][0],ny+i*in[a][1]);
	}
}
int main(){
	init();
	cin>>x>>y>>n;
	co=vi(n);
	in=vvi(n,vi(3));
	rep(i,n)rep(j,3)cin>>in[i][j];
	f(0,0,0);
	cout<<out<<endl;
}
0