結果

問題 No.822 Bitwise AND
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:06:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,739 bytes
コンパイル時間 461 ms
コンパイル使用メモリ 81,592 KB
実行使用メモリ 270,776 KB
最終ジャッジ日時 2025-04-15 23:08:34
合計ジャッジ時間 3,913 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    N, K = map(int, sys.stdin.readline().split())
    
    if N == 0:
        if K == 0:
            print(1)
        else:
            print("INF")
        return
    
    if K == 0:
        print(1)
        return
    
    # Check if N has two consecutive ones in binary representation
    has_consecutive_ones = False
    prev_one = False
    n = N
    while n > 0:
        bit = n & 1
        if bit == 1:
            if prev_one:
                has_consecutive_ones = True
                break
            prev_one = True
        else:
            prev_one = False
        n >>= 1
    
    if has_consecutive_ones:
        print("INF")
        return
    
    # Collect all bits in S (complement of N)
    bits = []
    m = 0
    while True:
        bit = 1 << m
        if (N & bit) == 0:
            bits.append(bit)
        m += 1
        if bit > N * 2 and m > 20:  # Heuristic to limit bits considered
            break
    
    # Dynamic Programming to count valid pairs
    from collections import defaultdict
    dp = defaultdict(int)
    dp[0] = 1
    
    for bit in bits:
        new_dp = defaultdict(int)
        for diff in dp:
            cnt = dp[diff]
            # Option 1: ignore the bit
            new_dp[diff] += cnt
            # Option 2: add to a (subtract bit)
            new_diff = diff - bit
            new_dp[new_diff] += cnt
            # Option 3: add to b (add bit, if within K)
            new_diff_add = diff + bit
            if new_diff_add <= K:
                new_dp[new_diff_add] += cnt
        dp = new_dp
    
    total = 0
    for diff in dp:
        if 0 <= diff <= K:
            total += dp[diff]
    
    print(total)

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