結果

問題 No.2237 Xor Sum Hoge
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:41:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,693 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 81,764 KB
実行使用メモリ 182,460 KB
最終ジャッジ日時 2025-04-16 16:43:54
合計ジャッジ時間 22,820 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353

def main():
    import sys
    input = sys.stdin.read
    N, B, C = map(int, input().split())

    # Precompute factorial, inverse, and inverse factorial modulo mod
    max_n = N
    fact = [1] * (max_n + 1)
    inv = [1] * (max_n + 1)
    fact_inv = [1] * (max_n + 1)
    for i in range(2, max_n + 1):
        fact[i] = fact[i-1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        fact_inv[i] = fact_inv[i-1] * inv[i] % mod

    # Precompute combination numbers C(n, k) mod mod
    comb_arr = [0] * (N + 1)
    for s in range(N + 1):
        if s > N:
            comb_arr[s] = 0
        else:
            comb_arr[s] = fact[N] * fact_inv[s] % mod * fact_inv[N - s] % mod

    from collections import defaultdict

    dp = defaultdict(int)
    dp[0] = 1

    for k in range(61):
        c_bit = (C >> k) & 1
        b_bit = (B >> k) & 1
        new_dp = defaultdict(int)
        for carry_in, cnt in dp.items():
            # Check if carry_in + c_bit ≡ b_bit mod 2
            if (carry_in + c_bit) % 2 != b_bit % 2:
                continue
            # Compute m = (carry_in + c_bit) // 2
            m = (carry_in + c_bit) // 2
            a_max = (N - c_bit) // 2
            # Iterate over possible a values
            for a in range(0, a_max + 1):
                s = 2 * a + c_bit
                if s > N:
                    break  # Since a_max is chosen such that s <= N, this should not happen
                carry_out = m + a
                new_dp[carry_out] = (new_dp[carry_out] + cnt * comb_arr[s]) % mod
        dp = new_dp
        if not dp:
            break

    print(dp.get(0, 0) % mod)

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