結果
問題 |
No.498 ワープクリスタル (給料日編)
|
ユーザー |
![]() |
提出日時 | 2020-02-02 14:49:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,727 bytes |
コンパイル時間 | 2,144 ms |
コンパイル使用メモリ | 197,124 KB |
最終ジャッジ日時 | 2025-01-08 21:50:26 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using PII = std::pair<int, int>; using PLL = std::pair<ll, ll>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) // #define DEBUG struct crystal{ int x; int y; int n; }; ll pow_mod(int p, int q, int mod) { ll ret, r; ret = 1; r = p; while (q > 0) { if (q % 2) { ret *= r; ret %= mod; } r = (r * r) % mod; q /= 2; } return ret % mod; } int main() { #ifdef DEBUG cout << "DEBUG MODE" << endl; ifstream in("input.txt"); //for debug cin.rdbuf(in.rdbuf()); //for debug #endif const int mod = 1e9+7; ll frac[76], frac_inv[16]; frac[0] = 1, frac_inv[0] = 1; rep2(i, 1, 76) frac[i] = (frac[i-1] * i) % mod; rep2(i, 1, 16) frac_inv[i] = ( frac_inv[i-1] * pow_mod(i, mod - 2, mod) ) % mod; int gx, gy, k, x, y, n, xsum, ysum; cin >> gx >> gy >> k; ll ans, s; vector<crystal> crystals; rep(i, k) { cin >> x >> y >> n; crystals.push_back( (crystal) {x, y, n} ); } rep(i, 5-k) crystals.push_back( (crystal) {0, 0, 0} ); ans = 0; rep(c0, crystals[0].n+1) rep(c1, crystals[1].n+1) rep(c2, crystals[2].n+1) rep(c3, crystals[3].n+1) rep(c4, crystals[4].n+1){ // cout << c0 << crystals[1].n+1 << c2 << c3 << c4 << "\n"; xsum = c0 * crystals[0].x + c1 * crystals[1].x + c2 * crystals[2].x + c3 * crystals[3].x + c4 * crystals[4].x; ysum = c0 * crystals[0].y + c1 * crystals[1].y + c2 * crystals[2].y + c3 * crystals[3].y + c4 * crystals[4].y; if (xsum == gx && ysum == gy) { s = 1; s *= frac[c0+c1+c2+c3+c4]; s *= frac_inv[c0]; s %= mod; s *= frac_inv[c1]; s %= mod; s *= frac_inv[c2]; s %= mod; s *= frac_inv[c3]; s %= mod; s *= frac_inv[c4]; s %= mod; ans += s; ans %= mod; // cout << s << "\n"; // cout << c0 << c1 << c2 << c3 << c4 << "\n"; } } cout << ans << endl; return 0; }