結果

問題 No.2237 Xor Sum Hoge
ユーザー gew1fw
提出日時 2025-06-12 21:36:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,592 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 160,776 KB
最終ジャッジ日時 2025-06-12 21:39:16
合計ジャッジ時間 22,814 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 998244353
MAX = 60000  # 6e4

# 预计算阶乘和逆阶乘
fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * (MAX + 1)
inv_fact[MAX] = pow(fact[MAX], MOD-2, MOD)
for i in range(MAX-1, -1, -1):
    inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

def main():
    N, B, C = map(int, sys.stdin.readline().split())
    
    if B < C or (B - C) % 2 != 0:
        print(0)
        return
    
    dp = defaultdict(int)
    dp[0] = 1  # 初始状态，处理到第0位，进位为0
    
    for i in range(61):  # 处理从0到60位
        new_dp = defaultdict(int)
        c_bit = (C >> i) & 1
        b_bit = (B >> i) & 1
        
        for c_in in dp:
            current = dp[c_in]
            # 检查条件：(b_bit + c_in + c_bit) % 2 == 0
            if (b_bit + c_in + c_bit) % 2 != 0:
                continue
            
            # s_i的可能值：s_i ≡ c_bit mod 2，0 <= s_i <= N
            min_s = c_bit % 2
            for s in range(min_s, N + 1, 2):
                # 计算c_out
                c_out = (s + c_in) // 2
                # 计算组合数
                cnt = comb(N, s)
                new_dp[c_out] = (new_dp[c_out] + current * cnt) % MOD
        
        dp = new_dp
        if not dp:
            break
    
    # 最终检查最高位+1位的进位是否为0
    print(dp.get(0, 0) % MOD)

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