結果
問題 | No.498 ワープクリスタル (給料日編) |
ユーザー | startcpp |
提出日時 | 2017-03-24 23:33:32 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,688 bytes |
コンパイル時間 | 665 ms |
コンパイル使用メモリ | 52,532 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-20 04:00:22 |
合計ジャッジ時間 | 2,106 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 12 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 13 ms
4,380 KB |
testcase_07 | AC | 13 ms
4,376 KB |
testcase_08 | AC | 13 ms
4,376 KB |
testcase_09 | AC | 12 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 3 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 2 ms
4,376 KB |
testcase_14 | AC | 1 ms
4,376 KB |
testcase_15 | AC | 1 ms
4,380 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 13 ms
4,380 KB |
testcase_19 | AC | 13 ms
4,380 KB |
testcase_20 | AC | 12 ms
4,376 KB |
testcase_21 | AC | 12 ms
4,376 KB |
testcase_22 | AC | 12 ms
4,376 KB |
testcase_23 | AC | 13 ms
4,376 KB |
testcase_24 | AC | 13 ms
4,376 KB |
ソースコード
//今いるところからの経路は何通り?と聞かれたら、「位置, 各クリスタルの残数」が分からないと答えられない。 //しかし, 各クリスタルを何個使うかさえわかれば, 使う順番によらず最終的な位置は同じになる。 //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); 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; }