結果

問題 No.2397 ω冪
ユーザー qwewe
提出日時 2025-05-14 13:08:28
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,753 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 68,668 KB
最終ジャッジ日時 2025-05-14 13:10:14
合計ジャッジ時間 4,518 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 RE * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Set a higher recursion depth limit to handle potentially deep recursive calls.
# The maximum length of the binary representation is 10^5. The depth of recursion might
# be related to this length, possibly linear in the worst case (e.g., N = 2^k - 1).
# A value like 2*10^5 + 100 should be safe for L=10^5.
# Use try-except block in case setting the limit fails (e.g., due to OS restrictions).
try:
    sys.setrecursionlimit(2 * 10**5 + 100) 
except Exception as e:
    # If setting the limit fails, print a warning to stderr. The program might still work
    # for smaller inputs or if the actual recursion depth is within the default limit.
    print(f"Warning: Could not set high recursion depth: {e}", file=sys.stderr)
    pass

# Memoization cache (dictionary) to store results of compare_int(N, M).
# Keys are tuples (N, M), values are boolean results (True if N < M, False otherwise).
memo = {}

def get_components_int(n):
    """
    Computes the components (N0, N1) for a positive integer n,
    where n is uniquely represented as n = (2 * N0 + 1) * 2^N1.
    N1 is the exponent of 2 in the prime factorization of n (v_2(n)).
    N0 = ( (n / 2^N1) - 1 ) / 2.
    Assumes n > 0.
    """
    # The function should not be called with n=0. The main comparison logic handles n=0 as a base case.
    if n == 0:
         raise ValueError("get_components_int called with 0") 

    # Find N1: the number of trailing zeros in the binary representation of n.
    # The expression (n & -n) isolates the lowest set bit. For n > 0, this value is 2^N1.
    # Example: n=12 (1100). -n is two's complement. In Python large ints it works conceptually.
    # -12 is ...11110100. n & -n = 1100 & ...0100 = 0100 = 4. Value is 2^2.
    lowest_set_bit = n & -n
    
    # The bit_length() method returns the number of bits required to represent an integer in binary, excluding the sign and leading zeros.
    # For a power of two, 2^k, its bit_length is k+1.
    # So, N1 = bit_length(2^N1) - 1.
    n1 = lowest_set_bit.bit_length() - 1
    
    # Calculate the odd part of n: temp_n = n / 2^N1
    # Right shifting by n1 performs integer division by 2^n1.
    temp_n = n >> n1
    
    # Compute N0 from the odd part temp_n. Since temp_n = 2*N0 + 1:
    # N0 = (temp_n - 1) / 2
    # Right shifting by 1 performs integer division by 2.
    N0_val = (temp_n - 1) >> 1
    
    # Return the computed components (N0, N1) as a tuple of integers.
    return (N0_val, N1_val)


def compare_int(N, M):
    """
    Recursively compares non-negative integers N and M based on the rule derived from the problem structure:
    N < M if and only if the pair (N1, N0) is lexicographically smaller than (M1, M0).
    Uses memoization to store results and avoid redundant computations.
    """
    
    # Create a state tuple (N, M) to use as a key in the memoization dictionary.
    state = (N, M)
    
    # Check if the result for this state is already in the cache.
    if state in memo:
        return memo[state]

    # Base cases for the recursion:
    if N == M:
        # If N equals M, then N is not strictly less than M.
        result = False
    elif N == 0:
        # If N is 0, and M must be non-zero (since N != M), then N < M is true.
        result = True
    elif M == 0:
        # If M is 0, and N must be non-zero (since N != M), then N < M is false.
        result = False
    else:
        # Recursive step: Both N > 0 and M > 0.
        
        # Compute components (N0, N1) for N and (M0, M1) for M.
        N0, N1 = get_components_int(N)
        M0, M1 = get_components_int(M)

        # Perform lexicographical comparison of pairs (N1, N0) and (M1, M0).
        # This means we compare N1 and M1 first. If they are equal, we compare N0 and M0.
        
        # Recursively compare N1 and M1.
        N1_lt_M1 = compare_int(N1, M1)
        
        if N1_lt_M1:
            # If N1 < M1, then the pair (N1, N0) is lexicographically smaller than (M1, M0).
            result = True
        else:
            # N1 >= M1. We need to determine if N1 == M1 or N1 > M1.
            # We can do this by checking the opposite comparison: M1 < N1.
            # Note: `compare_int(M1, N1)` might already be computed or will be computed and memoized.
            M1_lt_N1 = compare_int(M1, N1)
            
            # If N1 is not less than M1 (N1_lt_M1 is False) AND M1 is not less than N1 (M1_lt_N1 is False),
            # then N1 must be equal to M1.
            if not M1_lt_N1: 
                # Case N1 == M1: The comparison depends on N0 and M0.
                # Recursively compare N0 and M0. The result is True if N0 < M0.
                result = compare_int(N0, M0) 
            else:
                # Case N1 > M1 (since M1 < N1 is True).
                # The pair (N1, N0) is lexicographically larger than (M1, M0).
                result = False
            
    # Store the computed result in the memoization cache before returning.
    memo[state] = result
    return result

# Main execution block: reads input, calls the comparison function, and prints the result.
if __name__ == '__main__':
    # Read N and M from standard input. They are given as binary strings.
    N_bin = sys.stdin.readline().strip()
    M_bin = sys.stdin.readline().strip()

    # Convert the binary strings to Python's arbitrary precision integers.
    # Python handles large integers automatically.
    N = int(N_bin, 2)
    M = int(M_bin, 2)

    # Call the compare_int function to determine if N < M according to the problem's logic.
    if compare_int(N, M):
        # If compare_int returns True, it means N < M (which corresponds to f(N) \in f(M)).
        print("Yes")
    else:
        # Otherwise, N is not less than M.
        print("No")
0