結果
問題 | No.498 ワープクリスタル (給料日編) |
ユーザー |
![]() |
提出日時 | 2017-03-27 12:30:59 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 2,291 bytes |
コンパイル時間 | 1,283 ms |
コンパイル使用メモリ | 159,664 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 12:12:41 |
合計ジャッジ時間 | 2,048 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef vector<int> vint;typedef pair<int,int> pint;typedef vector<pint> vpint;#define rep(i,n) for(int i=0;i<(n);i++)#define REP(i,n) for(int i=n-1;i>=(0);i--)#define reps(i,f,n) for(int i=(f);i<(n);i++)#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)#define all(v) (v).begin(),(v).end()#define eall(v) unique(all(v), v.end())#define pb push_back#define mp make_pair#define fi first#define se second#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))const int MOD = 1e9 + 7;const int INF = 1e9;const ll INFF = 1e18;const int MAX_N = 200;ll inv[MAX_N + 10];ll fac[MAX_N + 10], facInv[MAX_N + 10];class MATH{public:MATH(){inverse();factroial();}ll nCk(ll n, ll k){// n! / k!*(n-k)!if(k < 0 || k > n) return 0;ll ret = fac[n];(ret *= facInv[k]) %= MOD;(ret *= facInv[n - k]) %= MOD;return ret;}ll nHk(ll n, ll k){// nHk = n+k-1 C k = (n+k-1)! / k! * (n-1)!if(n == 0 && k == 0) return 1;ll ret = fac[n + k - 1];(ret *= facInv[k]) %= MOD;(ret *= facInv[n - 1]) %= MOD;return ret;}ll nPk(ll n, ll k){//nPk = n! / (n-k)!if(k < 0 || k > n) return 0;ll ret = fac[n];(ret *= facInv[n - k]) %= MOD;return ret;}private:void inverse(void){inv[1] = 1;for (int i = 2; i <= MAX_N; ++i){// inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;}}void factroial(void){fac[0] = facInv[0] = 1;for (int i = 1; i <= MAX_N; ++i){fac[i] = (fac[i - 1] * i) % MOD;facInv[i] = (facInv[i - 1] * inv[i]) % MOD;}}};int Gx, Gy, K;int x[6], y[6], N[6];ll ans = 0;int use[10];void dfs(int cnt, int nx, int ny){if(cnt == K){if(nx == Gx && ny == Gy){// rep(i, cnt) printf("%d ", use[i]);ll n = 0, ret = 1;rep(i, cnt) n += use[i];ret *= fac[n];rep(i, cnt) if(use[i] != 0)ret *= facInv[use[i]], ret %= MOD;ans += ret; ans %= MOD;}return;}rep(i, N[cnt] + 1){use[cnt] = i;dfs(cnt + 1, nx + i * x[cnt], ny + i * y[cnt]);}}int main(void){cin >> Gx >> Gy >> K;rep(i, K) cin >> x[i] >> y[i] >> N[i];MATH mt;dfs(0, 0, 0);printf("%lld\n", ans);return 0;}