結果

問題 No.822 Bitwise AND
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:50:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,177 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 59,620 KB
最終ジャッジ日時 2025-06-12 15:50:26
合計ジャッジ時間 1,642 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, k = map(int, input().split())

if n == 0 and k >= 1:
    print("INF")
else:
    # Compute the bits not set in n (M's bits)
    m_bits = []
    for bit in range(31):
        if not (n & (1 << bit)):
            m_bits.append(bit)
    
    # Split into high and low bits
    high_bits = []
    low_bits = []
    for bit in m_bits:
        if (1 << bit) > k:
            high_bits.append(bit)
        else:
            low_bits.append(bit)
    
    # Process low bits in descending order
    low_bits.sort(reverse=True)
    
    # Initialize DP: dp[d] is the number of ways to get difference d
    dp = [0] * (k + 1)
    dp[0] = 1
    
    for bit in low_bits:
        new_dp = [0] * (k + 1)
        val = 1 << bit
        for d in range(k + 1):
            if dp[d] == 0:
                continue
            # Assign to a
            new_d = d - val
            if new_d >= 0 and new_d <= k:
                new_dp[new_d] += dp[d]
            # Assign to b
            new_d = d + val
            if new_d <= k:
                new_dp[new_d] += dp[d]
            # Assign to neither
            new_dp[d] += dp[d]
        dp = new_dp
    
    total = sum(dp)
    print(total)
0