結果

問題 No.2237 Xor Sum Hoge
ユーザー 👑 potato167
提出日時 2024-06-16 03:45:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 100 ms / 10,000 ms
コード長 2,424 bytes
コンパイル時間 3,771 ms
コンパイル使用メモリ 234,244 KB
最終ジャッジ日時 2025-02-21 23:01:19
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// in  : DFT(v) (len(v) = z)
// out : DFT(v) (len(v) = 2 * z)
template<class T>
void FPS_twice(std::vector<T> &v){
    int z = v.size();
    T e = (T(atcoder::internal::primitive_root_constexpr(T::mod()))).pow(T::mod() / (2 * z));
    auto cp = v;
    atcoder::internal::butterfly_inv(cp);
    T tmp = (T)(1) / (T)(z);
    for (int i = 0; i < z; i++){
        cp[i] *= tmp;
        tmp *= e;
    }
    atcoder::internal::butterfly(cp);
    for (int i = 0; i < z; i++) v.push_back(cp[i]);
};


// s.t |v| = 2 ^ s (no assert)
template<class T>
void FPS_pick_even_odd(std::vector<T> &v, int odd){
    int z = v.size() / 2;
    T half = (T)(1) / (T)(2);
    if (odd == 0){
        for (int i = 0; i < z; i++){
            v[i] = (v[i * 2] + v[i * 2 + 1]) * half;
        }
        v.resize(z);
    } else {
        T e = (T(atcoder::internal::primitive_root_constexpr(T::mod()))).pow(T::mod() / (2 * z));
        T ie = T(1) / e;
        std::vector<T> es = {half};
        while ((int)es.size() != z){
            std::vector<T> n_es((int)es.size() * 2);
            for (int i = 0; i < (int)es.size(); i++){
                n_es[i * 2] = (es[i]);
                n_es[i * 2 + 1] = (es[i] * ie);
            }
            ie *= ie;
            std::swap(n_es, es);
        }
        for (int i = 0; i < z; i ++){
            v[i] = (v[i * 2] - v[i * 2 + 1]) * es[i];
        }
        v.resize(z);
    }
}

int main(){
	long long N, B, C;
	cin >> N >> B >> C;
	// Binom
	vector<mint> fact(N + 1, 1), fact_inv(N + 1, 1);
	for (int i = 0; i < N; i++){
		fact[i + 1] = fact[i] * (i + 1);
	}
	fact_inv[N] = fact[N].inv();
	for (int i = N; i > 0; i--){
		fact_inv[i - 1] = fact_inv[i] * i;
	}
	int z = 8;
	while (z <= N) z *= 2;
	vector f(2, vector<mint>(z));
	for (int i = 0; i <= N; i++){
		f[i & 1][i / 2] = fact[N] * fact_inv[i] * fact_inv[N - i];
	}
	internal::butterfly(f[0]);
	internal::butterfly(f[1]);
	vector<mint> g(z, 1);
	int k = 0;
	for (int d = 0; d < 60; d++){
		FPS_pick_even_odd(g, 1 & (k + B + C));
		FPS_twice(g);
		for (int i = 0; i < z; i++){
			g[i] *= f[C & 1][i];
		}
		k = (k + 1 - (B & 1) + (C & 1)) / 2;
		B /= 2, C /= 2;
	}
	mint ans = 0;
	for (int i = 0; i < z; i++) ans += g[i];
	if (k) ans = 0;
	else ans /= z;
	cout << ans.val() << "\n";
}
0