#166635 (C++14) No.498 ワープクリスタル (給料日編)

• 問題: No.498 ワープクリスタル (給料日編)
• ユーザー: masa
• 提出日時: 2017-04-18 17:49:00
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 94 ms / 2,000 ms
• コード長: 1,274 bytes
• コンパイル時間: 612 ms
• コンパイル使用メモリ: 76,808 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-19 07:45:02
• 合計ジャッジ時間: 2,192 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	72 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	73 ms; 5,376 KB
testcase_07	AC	94 ms; 5,376 KB
testcase_08	AC	68 ms; 5,376 KB
testcase_09	AC	68 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	10 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	4 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	67 ms; 5,376 KB
testcase_19	AC	69 ms; 5,376 KB
testcase_20	AC	69 ms; 5,376 KB
testcase_21	AC	70 ms; 5,376 KB
testcase_22	AC	69 ms; 5,376 KB
testcase_23	AC	68 ms; 5,376 KB
testcase_24	AC	71 ms; 5,376 KB

ソースコード

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>

using namespace std;

const int mod = 1e9 + 7;

int calc(vector<int> uses) {
	int sum = accumulate(uses.begin(), uses.end(), 0);
	vector<int> nums;
	for (int i = sum; i > 1; i--) {
		nums.emplace_back(i);
	}

	for (auto e : uses) {
		for (int i = e; i > 1; i--) {
			int tmp = i;
			for (int j = 0; j < nums.size(); j++) {
				int gcd = __gcd(tmp, nums[j]);
				nums[j] /= gcd;
				tmp /= gcd;
				if (tmp == 1) {
					break;
				}
			}
		}
	}

	long long ret = 1;
	for (auto e : nums) {
		ret = (ret * e) % mod;
	}

	return ret;
}


int main() {
	int gx, gy, k;
	cin >> gx >> gy >> k;

	int limit = 1;
	vector<int> x(k), y(k), n(k);
	for (int i = 0; i < k; i++) {
		cin >> x[i] >> y[i] >> n[i];
		limit *= n[i] + 1;
	}

	long long ans = 0;
	for (int i = 0; i < limit; i++) {
		int tmp = i;
		int pos_x = 0;
		int pos_y = 0;

		vector<int> uses(k, 0);

		for (int j = 0; j < k; j++) {
			uses[j] = tmp % (n[j] + 1);
			pos_x += uses[j] * x[j];
			pos_y += uses[j] * y[j];
			tmp /= (n[j] + 1);
		}
		if (pos_x != gx || pos_y != gy) {
			continue;
		}

		// cout << calc(uses) << endl;
		ans = (ans + calc(uses)) % mod;
	}

	cout << ans << endl;
	return 0;
}