結果

問題 No.474 色塗り2
ユーザー koba-e964
提出日時 2016-12-24 13:20:48
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 338 ms
コード長 1,715 Byte
コンパイル時間 563 ms
使用メモリ 26,068 KB
最終ジャッジ日時 2019-12-05 00:52:26

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 24 ms
26,068 KB
2.txt AC 25 ms
26,068 KB
3.txt AC 24 ms
26,064 KB
large1.txt AC 338 ms
26,064 KB
sample.txt AC 25 ms
26,068 KB
テストケース一括ダウンロード

ソースコード

diff #
#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;
  }
}
0