結果
問題 | 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 DEBUGstruct 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 DEBUGcout << "DEBUG MODE" << endl;ifstream in("input.txt"); //for debugcin.rdbuf(in.rdbuf()); //for debug#endifconst 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;}