結果

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

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    N, B, C = map(int, sys.stdin.readline().split())
    
    # Precompute combination numbers C(N, x) mod MOD
    max_n = N
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD)
    for i in range(max_n-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    comb = [0] * (max_n + 1)
    for x in range(max_n + 1):
        if x < 0 or x > max_n:
            comb[x] = 0
        else:
            comb[x] = fact[max_n] * inv_fact[x] % MOD * inv_fact[max_n - x] % MOD
    
    # Initialize DP
    curr_dp = {0: 1}
    
    for k in range(61):  # Process each bit from 0 to 60
        next_dp = dict()
        s = (B >> k) & 1
        t = (C >> k) & 1
        
        for c_in, cnt in curr_dp.items():
            # Check if the parity condition is satisfied
            if (s != (c_in + t) % 2):
                continue
            
            # Calculate x's possible range
            x_min = max(0, s - c_in)
            x_max = N
            if x_min > x_max:
                continue
            
            # Determine c_out's range
            # x = 2*c_out + s - c_in
            # x >= x_min => 2*c_out >= x_min - (s - c_in)
            # c_out >= ceil( (x_min - (s - c_in)) / 2 )
            numerator = x_min - (s - c_in)
            c_out_min = (numerator + 1) // 2  # ceil division
            c_out_min = max(c_out_min, 0)
            
            # x <= x_max => 2*c_out <= x_max - (s - c_in)
            c_out_max = (x_max - (s - c_in)) // 2
            if c_out_min > c_out_max:
                continue
            
            # Iterate over possible c_out values
            for c_out in range(c_out_min, c_out_max + 1):
                x = 2 * c_out + s - c_in
                if x < 0 or x > N:
                    continue
                # Update next_dp
                if c_out not in next_dp:
                    next_dp[c_out] = 0
                next_dp[c_out] = (next_dp[c_out] + cnt * comb[x]) % MOD
        
        curr_dp = next_dp
        if not curr_dp:
            break  # Early exit if no possible states
    
    # After processing all bits, the carry must be 0
    print(curr_dp.get(0, 0) % MOD)

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