結果
問題 | No.498 ワープクリスタル (給料日編) |
ユーザー |
|
提出日時 | 2017-04-17 00:40:17 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 3,379 bytes |
コンパイル時間 | 662 ms |
コンパイル使用メモリ | 86,756 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 04:09:10 |
合計ジャッジ時間 | 1,775 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <map>#include <set>#include <utility>#include <string>#include <cstring>#include <queue>#include <cmath>#include <iomanip>#include <cassert>#include <numeric>#define EPS 1e-9#define INF 1070000000LL#define MOD 1000000007LL#define fir first#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)#define numa(x,a) for(auto x: a)#define ite iterator#define mp make_pair#define rep(i,n) rep2(i,0,n)#define rep2(i,m,n) for(int i=m;i<(n);i++)#define pb push_back#define pf push_front#define sec second#define sz(x) ((int)(x).size())#define ALL( c ) (c).begin(), (c).end()#define gcd(a,b) __gcd(a,b)#define mem(x,n) memset(x,n,sizeof(x))#define endl "\n"using namespace std;template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){}template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t);deploy<POS + 1, TUPLE, Ts...>(os, t); }template <class T,class U> std::ostream& operator<<(std::ostream &os, std::pair<T,U> &p){ os << "(" << p.first <<", " << p.second <<")";return os; }template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e <<(--remain == 0 ? "}" : ", "); return os; }template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain== 0 ? "}" : ", "); return os; }template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os <<"(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "}" : ", "); return os; }#define DEBUG1(var0) { std::cerr << (#var0) << "=" << (var0) << endl; }#define DEBUG2(var0, var1) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG1(var1); }#define DEBUG3(var0, var1, var2) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG2(var1,var2); }#define DEBUG4(var0, var1, var2, var3) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG3(var1,var2,var3); }using ll = long long;struct D {int x,y,n;};vector <D> data;ll ans = 0;ll C[100][100];void init(int n) {rep(i,n){C[i][i] = 1;C[i][0] = 1;}rep2(i,2,n + 1) {rep2(j,1,n+1) {C[i][j] = C[i-1][j-1] + C[i-1][j];if (C[i][j] >= MOD) {C[i][j] -= MOD;}}}}ll comb(int n, int r) {return C[n][r];}ll calc(const vector <int> &t) {ll n = accumulate(ALL(t), 0);ll ret = 1;int s = 0;numa(r, t) {ret *= comb(n-s, r);s += r;ret %= MOD;}return ret;}void go(int i, int n, int gx, int gy, vector <int> &t) {if (i == n) {int x = 0, y = 0;rep(j, n) {x += data[j].x * t[j];y += data[j].y * t[j];}if (x == gx && y == gy) {ans += calc(t);ans %= MOD;}return;}for (int j = 0; j <= data[i].n; j++) {t[i] = j;go(i+1, n, gx, gy, t);}return;}int main(){cin.tie(0);ios_base::sync_with_stdio(0);init(90);int gx, gy;int K;cin >> gx >> gy >> K;data.resize(K);for (auto &d : data) {cin >> d.x >> d.y >> d.n;}vector <int> times(K);go(0,K,gx,gy,times);cout << ans << endl;return 0;}