結果
問題 | No.474 色塗り2 |
ユーザー |
|
提出日時 | 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 |
ソースコード
import itertoolsdef init():N = 2 * 10**6vs = list(range(N + 1))vs[0] = 1p2 = [0] * (N + 1)n2 = 1while n2 <= N:n2 <<= 1for k in range(n2, N + 1, n2):vs[k] //= 2p2[k] += 1fac = 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, p2def mulmod(x, y):return (x * y) & 0b11111111111111111111def calc_fac(vs):fac = [1] * len(vs)f = 1mask = 2**20 - 1for i, v in enumerate(vs):f = (f * v) & maskfac[i] = freturn facdef calc_p2(p2):ans = [0] * len(p2)c = 0for i, p in enumerate(p2):c += pans[i] = creturn ansdef calc_inv(fac, vs):mod = 2**20mask = mod - 1N = 2 * 10**6inv = [1] * (N + 1)invc = 506201inv[N] = invcfor x in range(N - 1, 0, -1):invc = (invc * vs[x + 1]) & maskinv[x] = invcreturn invvs, fac, inv, p2 = init()def solve(A, B, C):if C % 2 == 0:return 0mask = 2**20 - 1if A & (combin(B + C - 1, B, mask) * C + mask):return 0else:return 1def 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 0return ((fac[n] * inv[a] * inv[b]) << tmp) & maskT = int(input())for t in range(T):A, B, C = map(int, input().split())print(solve(A, B, C))