結果
問題 | No.1258 コインゲーム |
ユーザー |
|
提出日時 | 2020-10-16 23:06:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 1,191 bytes |
コンパイル時間 | 693 ms |
コンパイル使用メモリ | 93,996 KB |
最終ジャッジ日時 | 2025-01-15 09:14:37 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <utility> #include <string> #include <queue> #include <stack> #include <map> using namespace std; typedef long long int ll; typedef pair<int, int> Pii; const ll mod = 1000000007; ll modpow(ll a, ll b, ll m = mod) { ll r = 1; while (b > 0) { if (b & 1) r = (r * a) % m; a = (a * a) % m; b >>= 1; } return r; } ll modinv(ll x, ll m = mod) { ll b = m; ll u = 1; ll v = 0; ll tmp; while (b) { ll t = x / b; x -= t * b; tmp = x; x = b; b = tmp; u -= t * v; tmp = u; u = v; v = tmp; } u %= m; if (u < 0) u += m; return u; } int main() { cin.tie(0); ios::sync_with_stdio(false); int s; cin >> s; vector<ll> n(s), m(s), x(s); for (int i = 0; i < s; i++) cin >> n[i] >> m[i] >> x[i]; vector<ll> ans(s); for (int i = 0; i < s; i++) { if (x[i]) ans[i] = ((modpow(m[i]+1, n[i]) - modpow(1-m[i], n[i])) % mod * modinv(2)) % mod; else ans[i] = ((modpow(1-m[i], n[i]) + modpow(m[i]+1, n[i])) % mod * modinv(2)) % mod; if (ans[i] < 0) ans[i] += mod; } for (auto &y: ans) cout << y << endl; return 0; }