結果

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

ソースコード

diff # 

//今いるところからの経路は何通り？と聞かれたら、「位置, 各クリスタルの残数」が分からないと答えられない。
//しかし, 各クリスタルを何個使うかさえわかれば, 使う順番によらず最終的な位置は同じになる。
//15^5は76万以下なので, 各クリスタルの個数を全探索する。
//あとは, 重複する数がある場合の順列組み合わせ問題{ex.11122333の並べ方～}を解いて足し合わせればよい。
#include <iostream>
#define int long long
using namespace std;

const int mod = 1000000007;
int fact[81];
int factInv[81];

int powmod(int a, int n, int mod) {
	if (n == 0) return 1;
	if (n % 2 == 0) return powmod((a * a) % mod, n / 2, mod) % mod;
	return (a * powmod(a, n - 1, mod)) % mod;
}

void init() {
	fact[0] = 1;
	for (int i = 1; i < 81; i++) fact[i] = (fact[i - 1] * i) % mod;
	factInv[0] = 1;
	for (int i = 1; i < 81; i++) factInv[i] = powmod(fact[i], mod - 2, mod);
}

int gx, gy, k;
int x[5], y[5], n[5];
int use[5];
int ans = 0;

void dfs(int id = 0) {
	int i;
	
	if (id == k) {
		int px = 0, py = 0;
		for (i = 0; i < k; i++) {
			px += x[i] * use[i];
			py += y[i] * use[i];
		}
		if (px == gx && py == gy) {
			int use_sum = 0;
			for (i = 0; i < k; i++) {
				use_sum += use[i];
			}
			int addNum = fact[use_sum];
			for (i = 0; i < k; i++) {
				addNum = (addNum * factInv[use[i]]) % mod;
			}
			ans = (ans + addNum) % mod;
		}
		return;
	}
	for (i = 0; i <= n[id]; i++) {
		use[id] = i;
		dfs(id + 1);
	}
}

signed main() {
	int i;
	cin >> gx >> gy >> k;
	for (i = 0; i < k; i++) cin >> x[i] >> y[i] >> n[i];
	init();
	dfs();
	cout << ans << endl;
	return 0;
}
0