結果
問題 | No.474 色塗り2 |
ユーザー |
|
提出日時 | 2016-12-24 13:20:48 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 267 ms / 2,000 ms |
コード長 | 1,715 bytes |
コンパイル時間 | 1,072 ms |
コンパイル使用メモリ | 70,180 KB |
実行使用メモリ | 28,028 KB |
最終ジャッジ日時 | 2024-12-14 17:18:26 |
合計ジャッジ時間 | 1,909 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
#include <algorithm> #include <cassert> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; ll powmod(ll x, ll e, ll mod) { ll sum = 1 % mod; ll cur = x % mod; while (e > 0) { if (e % 2 == 1) { sum = sum * cur % mod; } cur = cur * cur % mod; e /= 2; } return sum; } const ll mod = 1 << 21; ll residual[mod]; int pow2[mod]; void ll_precompute(void) { residual[0] = 1; pow2[0] = 0; REP(i, 1, mod) { ll r = i; int p = 0; while (r % 2 == 0) { r /= 2; p++; } residual[i] = residual[i - 1] * r % mod; pow2[i] = pow2[i - 1] + p; } } ll h_partial(int x, ll y) { if (x + y - 1 >= mod) { return 0; } if (y == 0) { return 0; } ll rem = 1; int p2 = pow2[x + y - 1] - pow2[x] - pow2[y - 1]; assert (p2 >= 0); rem = rem * residual[x + y - 1] % mod; rem = rem * powmod(residual[x], mod / 2 - 1, mod) % mod; rem = rem * powmod(residual[y - 1], mod / 2 - 1, mod) % mod; while (p2 > 0) { p2--; rem = rem * 2 % mod; } return rem; } int solve(int a, int b, int c) { if (c % 2 == 0) { return 0; } // H(a, c * H(b, c)) mod 2 ll rem = 1; // Computes H(b, c) rem = h_partial(b, c); rem = rem * c % mod; rem = h_partial(a, rem); return rem % 2; } int main(void){ int t; cin >> t; ll_precompute(); while (t--) { int a, b, c; cin >> a >> b >> c; cout << solve(a, b, c) << endl; } }