結果

問題 No.474 色塗り２
ユーザー Min_25Min_25
提出日時 2017-05-04 07:57:50
言語 PyPy2
(7.3.15)
結果
WA  
実行時間 -
コード長 919 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 76,988 KB
実行使用メモリ 124,220 KB
最終ジャッジ日時 2024-09-14 05:30:44
合計ジャッジ時間 2,416 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 172 ms
123,584 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 169 ms
123,784 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) + B - 1) % mod
    return 1 if (x & B) == B 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