結果

問題 No.474 色塗り２
ユーザー koba-e964koba-e964
提出日時 2016-12-24 13:03:21
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,653 bytes
コンパイル時間 899 ms
コンパイル使用メモリ 88,100 KB
実行使用メモリ 13,644 KB
最終ジャッジ日時 2024-12-14 17:18:24
合計ジャッジ時間 8,002 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
13,636 KB
testcase_01 AC 426 ms
9,892 KB
testcase_02 TLE -
testcase_03 TLE -
testcase_04 AC 158 ms
9,888 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#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 << 30;

ll h_partial(int x, ll y) {
  ll rem = 1;
  int pow2 = 0;
  if (y == 0) {
    return 0;
  }
  REP(i, 1, x + 1) {
    ll v = y - 1 + i;
    ll w = i;
    while (v % 2 == 0) {
      v /= 2;
      pow2++;
    }
    while (w % 2 == 0) {
      w /= 2;
      pow2--;
    }
    rem = rem * v % mod;
    rem = rem * powmod(w, mod / 2 - 1, mod) % mod;
  }
  while (pow2 > 0) {
    pow2--;
    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;
  int pow2 = 0;
  ll mod = 1 << 30;
  // Computes H(b, c)
  rem = h_partial(b, c);
  rem = rem * c % mod;
  rem = h_partial(a, rem);
  rem = rem * c % mod;
  return rem % 2;
}

int main(void){
  int t;
  cin >> t;
  while (t--) {
    int a, b, c;
    cin >> a >> b >> c;
    cout << solve(a, b, c) << endl;
  }
}
0