結果
問題 | No.474 色塗り2 |
ユーザー |
![]() |
提出日時 | 2017-05-04 08:03:01 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 280 ms / 2,000 ms |
コード長 | 919 bytes |
コンパイル時間 | 1,297 ms |
コンパイル使用メモリ | 76,552 KB |
実行使用メモリ | 125,304 KB |
最終ジャッジ日時 | 2024-09-14 06:07:16 |
合計ジャッジ時間 | 3,123 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
def solve():def inv(n):ret = nfor i in range(5):ret = ret * (2 - ret * n % mod) % modreturn retdef binom(n, m):ret = facts[n] * inv(facts[m] * facts[n - m] % mod) % modv = vs[n] - vs[m] - vs[n - m]ret = (ret << v) % modreturn retdef ctz(n):return (n & -n).bit_length() - 1def calc(A, B, C):if C % 2 == 0:return 0x = (C * binom(C - 1 + B, B) + A - 1) % modreturn 1 if (x & A) == A else 0N = 2 * 10 ** 6 + 20mod = 2 ** 30vs = [0] + [ctz(i) for i in range(1, N)]facts = [1] * Nfor i in range(1, N):facts[i] = facts[i - 1] * (i >> vs[i]) % modfor i in range(1, N):vs[i] += vs[i - 1]import sysinput = sys.stdin.readlineT = 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()