結果

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

ソースコード

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

    # 确定自由部分的位数
    free_bits = []
    bit = 1
    max_bit = 0
    while bit <= (1 << 20):  # 假设20位足够
        if (N & bit) == 0:
            free_bits.append(bit)
            if bit > max_bit:
                max_bit = bit
        bit <<= 1
    free_bits.sort(reverse=True)
    m = len(free_bits)
    if m == 0:
        # 检查x = y = N的情况
        if 0 <= (N - N) <= K:
            print(1)
        else:
            print(0)
        return

    # 动态规划初始化
    dp = [{} for _ in range(m+1)]
    dp[0][0] = 1

    for i in range(m):
        bit = free_bits[i]
        for d in dp[i]:
            count = dp[i][d]
            for a, b in [(0, 0), (0, 1), (1, 0)]:
                if a == 1 and b == 1:
                    continue  # 不满足a&b=0的条件
                if a == 0 and b == 0:
                    new_d = d
                elif a == 0 and b == 1:
                    new_d = d + bit
                else:  # a==1, b==0
                    new_d = d - bit
                if -K <= new_d <= K:
                    if new_d in dp[i+1]:
                        dp[i+1][new_d] += count
                    else:
                        dp[i+1][new_d] = count

    total = 0
    for d in dp[m]:
        if d <= K and d >= 0:
            total += dp[m][d]
    print(total)

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