結果

問題 No.822 Bitwise AND
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:52:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,787 bytes
記録
コンパイル時間 303 ms
コンパイル使用メモリ 82,148 KB
実行使用メモリ 63,476 KB
最終ジャッジ日時 2025-03-26 15:53:31
合計ジャッジ時間 1,918 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from functools import lru_cache

def main():
    N, K = map(int, sys.stdin.readline().split())
    if N == 0:
        if K >= 1:
            print("INF")
        else:
            print(1)
        return

    # Collect the positions of 0 bits in N (sorted from highest to lowest)
    bits = []
    mask = ~N
    for i in reversed(range(20)):  # Check up to 20 bits
        if (mask >> i) & 1:
            bits.append(i)
    bits = sorted(bits, reverse=True)  # Process highest bits first

    if not bits:
        print(1 if K >= 0 else 0)
        return

    # Precompute the maximum possible addition from remaining bits
    max_add = [0] * (len(bits) + 1)
    for i in range(len(bits)-1, -1, -1):
        max_add[i] = max_add[i+1] + (1 << bits[i])

    @lru_cache(maxsize=None)
    def dfs(pos, delta, state):
        if pos == len(bits):
            return 1 if 0 <= delta <= K else 0

        current_bit = bits[pos]
        sum_rest = max_add[pos+1]

        total = 0

        # Option 1: Set bit in a (only if state is 'lt')
        if state == 1:  # state 1 is 'lt'
            new_d = delta - (1 << current_bit)
            if new_d <= K:
                total += dfs(pos + 1, new_d, 1)

        # Option 2: Set bit in b
        new_d = delta + (1 << current_bit)
        new_state = state
        if state == 0:  # state 0 is 'eq'
            new_state = 1
        # Check if adding remaining bits could exceed K
        if new_d + sum_rest <= K:
            total += dfs(pos + 1, new_d, new_state)
        elif new_d <= K:
            total += dfs(pos + 1, new_d, new_state)

        # Option 3: Do not set the bit
        total += dfs(pos + 1, delta, state)

        return total

    result = dfs(0, 0, 0)
    print(result)

if __name__ == "__main__":
    main()
0