結果
問題 | No.474 色塗り2 |
ユーザー |
![]() |
提出日時 | 2016-12-22 00:17:57 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,733 bytes |
コンパイル時間 | 309 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 350,460 KB |
最終ジャッジ日時 | 2024-12-14 14:29:49 |
合計ジャッジ時間 | 14,856 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | TLE * 1 |
other | TLE * 4 |
ソースコード
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 = [0] * modfact_mod = [0] * modfact_mod[0] = 1for i in range(1, mod):j = if2 = 0while j % 2 == 0:f2 += 1j = j // 2fact_mod[i] = fact_mod[i-1] * j % modfact_factor2[i] = fact_factor2[i-1] + f2# totient# totient_table = [0] * mod# for i in range(1, mod):# totient_table[i] = i# for i in range(1, mod):# if totient_table[i] == i:# for j in range(i, mod, i):# totient_table[j] = totient_table[j] // i * (i - 1)# def minv2(n, m):# return pow(n, totient_table[m] - 1, m)def totient(n):res = nfor i in range(2, n):if i*i > n:breakif n % i == 0:res = res // i * (i - 1)while n % i == 0:n = n // iif n != 1:res = res // n * (n - 1)return restotient_mod = totient(mod)def minv2(n):return pow(n, totient_mod - 1, mod)def solve(A, B, C):if C % 2 == 0: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 = fact_mod[C+B-1] * minv2(fact_mod[B]) % mod * minv2(fact_mod[C-1]) % modval = ((C * val % mod) << min(32, f2)) % mod + A - 1print(f2, val)if (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))