結果
問題 | No.474 色塗り2 |
ユーザー |
![]() |
提出日時 | 2016-12-21 23:28:48 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 970 bytes |
コンパイル時間 | 196 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 244,848 KB |
最終ジャッジ日時 | 2024-12-14 14:29:17 |
合計ジャッジ時間 | 2,494 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 3 WA * 1 |
ソースコード
def ext_gcd(a, b):if b == 0:return [1, 0]else:y, x = ext_gcd(b, a % b)return [x, y - (a // b) * x]def minv(n, m):return ext_gcd(n, m)[0]mod = 2 ** 21fact_factor2 = list()fact_mod = list()fact_factor2.append(0)fact_mod.append(1)for i in range(1, mod):j = if2 = 0while j % 2 == 0:f2 += 1j = j // 2fact_mod.append(fact_mod[i-1] * j % mod)fact_factor2.append(fact_factor2[i-1] + f2)def solve(A, B, C):if C == 2:return 0else:f2 = fact_factor2[C+B-1] - fact_factor2[B] - fact_factor2[C-1]val = fact_mod[C+B-1] * minv(fact_mod[B], mod) % mod * minv(fact_mod[C-1], mod) % modval = ((C * val % mod) << min(32, f2)) % mod + A - 1if (val & A) == A:return 1else:return 0testcase = int(input())for _ in range(testcase):A, B, C = list(map(int, input().split()))print(solve(A, B, C))