結果

問題 No.2237 Xor Sum Hoge
コンテスト
ユーザー 👑 potato167
提出日時 2025-04-17 11:16:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 551 ms / 10,000 ms
コード長 1,423 bytes
コンパイル時間 3,986 ms
コンパイル使用メモリ 232,636 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-17 11:16:41
合計ジャッジ時間 15,112 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/convolution>
#include <atcoder/modint>
using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll B, C;
    cin >> N >> B >> C;

    // Precompute factorials and inv factorials up to N
    vector<mint> fact(N+1), invfact(N+1);
    fact[0] = 1;
    for(int i = 1; i <= N; i++) fact[i] = fact[i-1] * i;
    invfact[N] = fact[N].inv();
    for(int i = N; i >= 1; i--) invfact[i-1] = invfact[i] * i;

    // dp[c] = number of ways with carry = c at current bit
    vector<mint> dp(N+1), dp2;
    dp[0] = 1;

    for(int k = 0; k < 60; k++){
        int b = (B >> k) & 1;
        int x = (C >> k) & 1;

        // Build f: f[ct] = C(N, ct) if ct % 2 == x, else 0
        vector<mint> f(N+1);
        for(int ct = x; ct <= N; ct += 2){
            f[ct] = fact[N] * invfact[ct] * invfact[N-ct];
        }

        // Convolution of dp and f
        auto conv = atcoder::convolution(dp, f);

        // Build next dp2: dp2[new_carry] = conv[2*new_carry + b]
        dp2.assign(N+1, 0);
        int M = (int)conv.size();
        for(int c = 0; c <= N; c++){
            int idx = 2*c + b;
            if(idx < M) dp2[c] = conv[idx];
        }

        dp.swap(dp2);
    }

    // Answer is dp[0] (no carry out after highest bit)
    cout << dp[0].val() << "\n";
    return 0;
}
0