結果

問題 No.474 色塗り2
ユーザー rpy3cpprpy3cpp
提出日時 2017-01-11 18:51:30
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,732 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 324,312 KB
最終ジャッジ日時 2024-12-21 09:51:58
合計ジャッジ時間 12,016 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 3 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import itertools
def init():
N = 2 * 10**6
vs = list(range(N + 1))
vs[0] = 1
p2 = [0] * (N + 1)
n2 = 1
while n2 <= N:
n2 <<= 1
for k in range(n2, N + 1, n2):
vs[k] //= 2
p2[k] += 1
fac = calc_fac(vs)
# p2 = calc_p2(p2)
# fac = list(itertools.accumulate(vs, lambda x, y: (x * y) & 0b11111111111111111111))
# fac = list(itertools.accumulate(vs, mulmod))
p2 = list(itertools.accumulate(p2))
inv = calc_inv(fac, vs)
return vs, fac, inv, p2
def mulmod(x, y):
return (x * y) & 0b11111111111111111111
def calc_fac(vs):
fac = [1] * len(vs)
f = 1
mask = 2**20 - 1
for i, v in enumerate(vs):
f = (f * v) & mask
fac[i] = f
return fac
def calc_p2(p2):
ans = [0] * len(p2)
c = 0
for i, p in enumerate(p2):
c += p
ans[i] = c
return ans
def calc_inv(fac, vs):
mod = 2**20
mask = mod - 1
N = 2 * 10**6
inv = [1] * (N + 1)
invc = 506201
inv[N] = invc
for x in range(N - 1, 0, -1):
invc = (invc * vs[x + 1]) & mask
inv[x] = invc
return inv
vs, fac, inv, p2 = init()
def solve(A, B, C):
if C % 2 == 0:
return 0
mask = 2**20 - 1
if A & (combin(B + C - 1, B, mask) * C + mask):
return 0
else:
return 1
def combin(n, b, mask):
a = n - b
# p2num = p2[n]
# p2den1 = p2[a]
# p2den2 = p2[b]
# valnum = fac[n]
# valden1 = inv[a]
# valden2 = inv[b]
tmp = p2[n] - p2[a] - p2[b]
if tmp >= 20:
return 0
return ((fac[n] * inv[a] * inv[b]) << tmp) & mask
T = int(input())
for t in range(T):
A, B, C = map(int, input().split())
print(solve(A, B, C))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0