結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 998244353

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

    # Precompute factorial and inverse factorial modulo MOD
    fact = [1] * (N + 1)
    for i in range(1, N + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (N + 1)
    inv_fact[N] = pow(fact[N], MOD - 2, MOD)
    for i in range(N - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    comb_table = [0] * (N + 1)
    for t in range(N + 1):
        comb_table[t] = fact[N] * inv_fact[t] % MOD * inv_fact[N - t] % MOD

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

    for k in range(61):
        b_k = (B >> k) & 1
        s_k = (C >> k) & 1
        curr_dp = defaultdict(int)
        for c_in, cnt in prev_dp.items():
            if (c_in + s_k) % 2 != b_k % 2:
                continue
            numerator_min = c_in - b_k
            c_new_min = max((numerator_min + 1) // 2, 0)
            numerator_max = N + c_in - b_k
            c_new_max = numerator_max // 2
            if c_new_min > c_new_max:
                continue
            for c_new in range(c_new_min, c_new_max + 1):
                t = b_k + 2 * c_new - c_in
                if t < 0 or t > N:
                    continue
                if (t % 2) != s_k % 2:
                    continue
                curr_dp[c_new] = (curr_dp[c_new] + cnt * comb_table[t]) % MOD
        prev_dp = curr_dp

    print(prev_dp.get(0, 0) % MOD)

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