結果

問題 No.474 色塗り２
ユーザー Min_25Min_25
提出日時 2017-05-04 08:03:01
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 277 ms / 2,000 ms
コード長 919 bytes
コンパイル時間 1,057 ms
コンパイル使用メモリ 77,860 KB
実行使用メモリ 126,836 KB
最終ジャッジ日時 2023-10-12 06:48:06
合計ジャッジ時間 2,681 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 155 ms
125,036 KB
testcase_01 AC 156 ms
126,836 KB
testcase_02 AC 158 ms
125,052 KB
testcase_03 AC 277 ms
126,608 KB
testcase_04 AC 156 ms
125,196 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
  def inv(n):
    ret = n
    for i in range(5):
      ret = ret * (2 - ret * n % mod) % mod
    return ret

  def binom(n, m):
    ret = facts[n] * inv(facts[m] * facts[n - m] % mod) % mod
    v = vs[n] - vs[m] - vs[n - m]
    ret = (ret << v) % mod
    return ret

  def ctz(n):
    return (n & -n).bit_length() - 1

  def calc(A, B, C):
    if C % 2 == 0:
      return 0
    x = (C * binom(C - 1 + B, B) + A - 1) % mod
    return 1 if (x & A) == A else 0

  N = 2 * 10 ** 6 + 20
  mod = 2 ** 30

  vs = [0] + [ctz(i) for i in range(1, N)]
  facts = [1] * N
  for i in range(1, N):
    facts[i] = facts[i - 1] * (i >> vs[i])  % mod
  for i in range(1, N):
    vs[i] += vs[i - 1]

  import sys
  input = sys.stdin.readline
  T = int(input())
  results = []
  for _ in range(T):
    a, b, c = map(int, input().split())
    results += [calc(a, b, c)]
  print("\n".join([`ans` for ans in results]))

solve()
0