結果

問題 No.474 色塗り２
ユーザー qwewe
提出日時 2025-05-14 13:17:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,383 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 76,512 KB
最終ジャッジ日時 2025-05-14 13:18:41
合計ジャッジ時間 1,180 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Using Python's built-in pow for modular exponentiation which is typically fast and reliable.
# It computes (base^power) % modulus.

# Function to solve a single test case
def solve():
    # Read A, B, C from input line
    A, B, C = map(int, sys.stdin.readline().split())

    # The problem asks for the number of distinct colorings modulo 2.
    # The number of distinct colorings N is given by N = C * Binomial(C^(1+B) + A - 1, A).
    # We need to compute N mod 2.

    # Case 1: C is even.
    # If C is even, C = 0 (mod 2).
    # N = C * ... = 0 * ... = 0 (mod 2).
    if C % 2 == 0:
        print(0)
    
    # Case 2: C is odd.
    # If C is odd, C = 1 (mod 2).
    # N = 1 * Binomial(C^(1+B) + A - 1, A) (mod 2)
    # N = Binomial(C^(1+B) + A - 1, A) (mod 2).
    else:
        # Subcase 2.1: C = 1.
        # If C = 1, then C is odd.
        # N = Binomial(1^(1+B) + A - 1, A) (mod 2)
        # N = Binomial(1 + A - 1, A) (mod 2)
        # N = Binomial(A, A) (mod 2)
        # Since A >= 1, Binomial(A, A) = 1.
        # So N = 1 (mod 2).
        if C == 1:
            print(1)
        
        # Subcase 2.2: C is odd and C > 1.
        # We need to compute Binomial(C^(1+B) + A - 1, A) mod 2.
        # By Lucas's Theorem property for modulo 2:
        # Binomial(n, k) = 1 (mod 2) if and only if (k & (n-k)) == 0.
        # Here, n = C^(1+B) + A - 1 and k = A.
        # n - k = (C^(1+B) + A - 1) - A = C^(1+B) - 1.
        # So, Binomial(C^(1+B) + A - 1, A) = 1 (mod 2) if and only if (A & (C^(1+B) - 1)) == 0.
        else:
            # We need to check the condition (A & (C^(B+1) - 1)) == 0.
            # Since C^(B+1) - 1 can be very large, we only need its value modulo 2^k where 2^k > A.
            # The maximum value of A is 10^6.
            # We know 2^19 = 524288 and 2^20 = 1048576.
            # Since A <= 10^6, A < 2^20. So checking the condition modulo 2^20 is sufficient.
            # Any higher bits of C^(B+1) - 1 would not affect the bitwise AND with A.
            
            k = 20 # Sufficient bit length since A <= 10^6 < 2^20
            modulus = 1 << k # 2^k = 1048576
            
            # Calculate the exponent B+1.
            exponent = B + 1
            
            # Compute C^(B+1) % 2^k using modular exponentiation.
            # Python's built-in pow(base, exponent, modulus) is efficient.
            C_pow_B1 = pow(C, exponent, modulus)
            
            # Compute (C^(B+1) - 1) % 2^k.
            # We add modulus before taking the final modulo to ensure the result is non-negative
            # if C_pow_B1 happens to be 0 or 1.
            # Since C is odd and modulus=2^k (k>=1), C_pow_B1 will be odd. 
            # C_pow_B1 - 1 will be even.
            X_mod_2k = (C_pow_B1 - 1 + modulus) % modulus
            
            # Check the condition: (A & X_mod_2k) == 0
            # If the bitwise AND is 0, it means there is no position 'i' where both A and (C^(B+1)-1) have the i-th bit set.
            # This corresponds to Binomial coefficient being odd (1 mod 2).
            if (A & X_mod_2k) == 0:
                print(1)
            # If the bitwise AND is non-zero, it means the Binomial coefficient is even (0 mod 2).
            else:
                print(0)

# Read the number of test cases
T = int(sys.stdin.readline())
# Process each test case
for _ in range(T):
    solve()
0