結果
| 問題 | No.2237 Xor Sum Hoge |
| ユーザー |
👑  rin204
|
| 提出日時 | 2023-03-03 23:01:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,414 ms / 10,000 ms |
| コード長 | 20,684 bytes |
| コンパイル時間 | 2,628 ms |
| コンパイル使用メモリ | 214,216 KB |
| 最終ジャッジ日時 | 2025-02-11 04:11:23 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 |
ソースコード
#line 1 "A.cpp"// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;template <class T>using pq = priority_queue<T>;template <class T>using qp = priority_queue<T, vector<T>, greater<T>>;#define vec(T, A, ...) vector<T> A(__VA_ARGS__);#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));#ifndef RIN__LOCAL#define endl "\n"#endif#define spa ' '#define len(A) A.size()#define all(A) begin(A), end(A)#define fori1(a) for(ll _ = 0; _ < (a); _++)#define fori2(i, a) for(ll i = 0; i < (a); i++)#define fori3(i, a, b) for(ll i = (a); i < (b); i++)#define fori4(i, a, b, c) for(ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))#define overload4(a, b, c, d, e, ...) e#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)template <typename T>vector<tuple<ll, T>> ENUMERATE(vector<T> &A, ll s = 0){vector<tuple<ll, T>> ret(A.size());for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};return ret;}vector<tuple<ll, char>> ENUMERATE(string &A, ll s = 0){vector<tuple<ll, char>> ret(A.size());for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};return ret;}#define enum1(A) fori(A.size())#define enum2(a, A) for(auto a:A)#define enum3(i, a, A) for(auto&& [i, a]: ENUMERATE(A))#define enum4(i, a, A, s) for(auto&& [i, a]: ENUMERATE(A, s))#define enum(...) overload4(__VA_ARGS__, enum4, enum3, enum2, enum1)(__VA_ARGS__)template <typename T, typename S>vector<tuple<T, S>> ZIP(vector<T> &A, vector<S> &B){int n = min(A.size(), B.size());vector<tuple<T, S>> ret(n);for(int i = 0; i < n; i++) ret[i] = {A[i], B[i]};return ret;}template <typename T, typename S>vector<tuple<ll, T, S>> ENUMZIP(vector<T> &A, vector<S> &B, ll s = 0){int n = min(A.size(), B.size());vector<tuple<ll, T, S>> ret(n);for(int i = 0; i < n; i++) ret[i] = {i + s, A[i], B[i]};return ret;}#define zip4(a, b, A, B) for(auto&& [a, b]: ZIP(A, B))#define enumzip5(i, a, b, A, B) for(auto&& [i, a, b]: ENUMZIP(A, B))#define enumzip6(i, a, b, A, B, s) for(auto&& [i, a, b]: ENUMZIP(A, B, s))#define overload6(a, b, c, d, e, f, g, ...) g#define zip(...) overload6(__VA_ARGS__, enumzip6, enumzip5, zip4, _, _, _)(__VA_ARGS__)vector<char> stoc(string &S){int n = S.size();vector<char> ret(n);for(int i = 0; i < n; i++) ret[i] = S[i];return ret;}#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);#define VEC(T, A, n) vector<T> A(n); inp(A);#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);const ll MOD1 = 1000000007;const ll MOD9 = 998244353;template<class T> auto min(const T& a){return *min_element(all(a));}template<class T> auto max(const T& a){return *max_element(all(a));}template <class T, class S>inline bool chmax(T &a, const S &b) {return (a < b ? a = b, 1 : 0);}template <class T, class S>inline bool chmin(T &a, const S &b) {return (a > b ? a = b, 1 : 0);}void FLUSH(){cout << flush;}void print(){cout << endl;}template <class Head, class... Tail>void print(Head &&head, Tail &&... tail) {cout << head;if (sizeof...(Tail)) cout << spa;print(forward<Tail>(tail)...);}template<typename T>void print(vector<T> &A){int n = A.size();for(int i = 0; i < n; i++){cout << A[i];if(i != n - 1) cout << ' ';}cout << endl;}template<typename T>void print(vector<vector<T>> &A){for(auto &row: A) print(row);}template<typename T, typename S>void print(pair<T, S> &A){cout << A.first << spa << A.second << endl;}template<typename T, typename S>void print(vector<pair<T, S>> &A){for(auto &row: A) print(row);}template<typename T, typename S>void prisep(vector<T> &A, S sep){int n = A.size();for(int i = 0; i < n; i++){cout << A[i];if(i == n - 1) cout << endl;else cout << sep;}}template<typename T, typename S>void priend(T A, S end){cout << A << end;}template<typename T>void priend(T A){priend(A, spa);}template<class... T>void inp(T&... a){(cin >> ... >> a);}template<typename T>void inp(vector<T> &A){for(auto &a:A) cin >> a;}template<typename T>void inp(vector<vector<T>> &A){for(auto &row:A) inp(row);}template<typename T, typename S>void inp(pair<T, S> &A){inp(A.first, A.second);}template<typename T, typename S>void inp(vector<pair<T, S>> &A){for(auto &row: A) inp(row.first, row.second);}template<typename T>T sum(vector<T> &A){T tot = 0;for(auto a:A) tot += a;return tot;}template<typename T>pair<vector<T>, map<T, int>> compression(vector<T> X){sort(all(X));X.erase(unique(all(X)), X.end());map<T, int> mp;for(int i = 0; i < X.size(); i++) mp[X[i]] = i;return {X, mp};}#line 2 "Library/C++/other/Modint.hpp"template<int MOD>struct Modint{int x;Modint() : x(0){}Modint(int64_t y){if(y >= 0) x = y % MOD;else x = (y % MOD + MOD) % MOD;}Modint &operator+=(const Modint &p){x += p.x;if(x >= MOD) x -= MOD;return *this;}Modint &operator-=(const Modint &p){x -= p.x;if(x < 0) x += MOD;return *this;}Modint &operator*=(const Modint &p){x = int(1LL * x * p.x % MOD);return *this;}Modint &operator/=(const Modint &p){*this *= p.inverse();return *this;}Modint &operator%=(const Modint &p){assert(p.x == 0);return *this;}Modint operator-() const{return Modint(-x);}Modint& operator++() {x++;if (x == MOD) x = 0;return *this;}Modint& operator--() {if (x == 0) x = MOD;x--;return *this;}Modint operator++(int) {Modint result = *this;++*this;return result;}Modint operator--(int) {Modint result = *this;--*this;return result;}friend Modint operator+(const Modint &lhs, const Modint &rhs){return Modint(lhs) += rhs;}friend Modint operator-(const Modint &lhs, const Modint &rhs){return Modint(lhs) -= rhs;}friend Modint operator*(const Modint &lhs, const Modint &rhs){return Modint(lhs) *= rhs;}friend Modint operator/(const Modint &lhs, const Modint &rhs){return Modint(lhs) /= rhs;}friend Modint operator%(const Modint &lhs, const Modint &rhs){assert(rhs.x == 0);return Modint(lhs);}bool operator==(const Modint &p) const{return x == p.x;}bool operator!=(const Modint &p) const{return x != p.x;}bool operator<(const Modint &rhs) {return x < rhs.x;}bool operator<=(const Modint &rhs) {return x <= rhs.x;}bool operator>(const Modint &rhs) {return x > rhs.x;}bool operator>=(const Modint &rhs) {return x >= rhs.x;}Modint inverse() const{int a = x, b = MOD, u = 1, v = 0, t;while(b > 0){t = a / b;a -= t * b;u -= t * v;swap(a, b);swap(u, v);}return Modint(u);}Modint pow(int64_t k) const{Modint ret(1);Modint y(x);while(k > 0){if(k & 1) ret *= y;y *= y;k >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const Modint &p){return os << p.x;}friend istream &operator>>(istream &is, Modint &p){int64_t y;is >> y;p = Modint<MOD>(y);return (is);}static int get_mod(){return MOD;}};struct Arbitrary_Modint{int x;static int MOD;static void set_mod(int mod){MOD = mod;}Arbitrary_Modint() : x(0){}Arbitrary_Modint(int64_t y){if(y >= 0) x = y % MOD;else x = (y % MOD + MOD) % MOD;}Arbitrary_Modint &operator+=(const Arbitrary_Modint &p){x += p.x;if(x >= MOD) x -= MOD;return *this;}Arbitrary_Modint &operator-=(const Arbitrary_Modint &p){x -= p.x;if(x < 0) x += MOD;return *this;}Arbitrary_Modint &operator*=(const Arbitrary_Modint &p){x = int(1LL * x * p.x % MOD);return *this;}Arbitrary_Modint &operator/=(const Arbitrary_Modint &p){*this *= p.inverse();return *this;}Arbitrary_Modint &operator%=(const Arbitrary_Modint &p){assert(p.x == 0);return *this;}Arbitrary_Modint operator-() const{return Arbitrary_Modint(-x);}Arbitrary_Modint& operator++() {x++;if (x == MOD) x = 0;return *this;}Arbitrary_Modint& operator--() {if (x == 0) x = MOD;x--;return *this;}Arbitrary_Modint operator++(int) {Arbitrary_Modint result = *this;++*this;return result;}Arbitrary_Modint operator--(int) {Arbitrary_Modint result = *this;--*this;return result;}friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){return Arbitrary_Modint(lhs) += rhs;}friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){return Arbitrary_Modint(lhs) -= rhs;}friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){return Arbitrary_Modint(lhs) *= rhs;}friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){return Arbitrary_Modint(lhs) /= rhs;}friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){assert(rhs.x == 0);return Arbitrary_Modint(lhs);}bool operator==(const Arbitrary_Modint &p) const{return x == p.x;}bool operator!=(const Arbitrary_Modint &p) const{return x != p.x;}bool operator<(const Arbitrary_Modint &rhs) {return x < rhs.x;}bool operator<=(const Arbitrary_Modint &rhs) {return x <= rhs.x;}bool operator>(const Arbitrary_Modint &rhs) {return x > rhs.x;}bool operator>=(const Arbitrary_Modint &rhs) {return x >= rhs.x;}Arbitrary_Modint inverse() const{int a = x, b = MOD, u = 1, v = 0, t;while(b > 0){t = a / b;a -= t * b;u -= t * v;swap(a, b);swap(u, v);}return Arbitrary_Modint(u);}Arbitrary_Modint pow(int64_t k) const{Arbitrary_Modint ret(1);Arbitrary_Modint y(x);while(k > 0){if(k & 1) ret *= y;y *= y;k >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const Arbitrary_Modint &p){return os << p.x;}friend istream &operator>>(istream &is, Arbitrary_Modint &p){int64_t y;is >> y;p = Arbitrary_Modint(y);return (is);}static int get_mod(){return MOD;}};int Arbitrary_Modint::MOD = 998244353;using modint9 = Modint<998244353>;using modint1 = Modint<1000000007>;using modint = Arbitrary_Modint;#line 188 "A.cpp"using mint = modint9;#line 2 "Library/C++/math/modinv.hpp"template<typename T>T modinv(T a, T MOD){T b = MOD;T u = 1;T v = 0;while(b > 0){T t = a / b;a -= t * b;u -= t * v;swap(a, b);swap(u, v);}if(a != 1) return -1;if(u < 0) u += MOD;return u;}#line 3 "Library/C++/math/Combination.hpp"template <typename T>struct Combination{int N;vector<T> fact, invfact;Combination(int N) : N(N){fact.resize(N + 1);invfact.resize(N + 1);fact[0] = 1;for(int i = 1; i <= N; i++){fact[i] = fact[i - 1] * i;}invfact[N] = T(1) / fact[N];for(int i = N - 1; i >= 0; i--){invfact[i] = invfact[i + 1] * (i + 1);}}T nCk(int n, int k){assert(0 <= n && n <= N);if(k > n || k < 0) return T(0);return fact[n] * invfact[k] * invfact[n - k];}T nPk(int n, int k){assert(0 <= n && n <= N);if(k > n || k < 0) return T(0);return fact[n] * invfact[n - k];}T nHk(int n, int k){if(n == 0 && k == 0) return T(1);return nCk(n + k - 1, k);}};#line 2 "Library/C++/convolution/NTT.hpp"template<typename mint>struct NumberTheoreticTransform{static vector<mint> roots, iroots, rate3, irate3;static int max_base;NumberTheoreticTransform() = default;static void init(){if(!roots.empty()) return;const unsigned mod = mint::get_mod();auto tmp = mod - 1;max_base = 0;while(tmp % 2 == 0){tmp >>= 1;max_base++;}mint root = 2;while(root.pow((mod - 1) >> 1) == 1) root++;roots.resize(max_base + 1);iroots.resize(max_base + 1);rate3.resize(max_base + 1);irate3.resize(max_base + 1);roots[max_base] = root.pow((mod - 1) >> max_base);iroots[max_base] = mint(1) / roots[max_base];for(int i = max_base - 1; i >= 0; i--){roots[i] = roots[i + 1] * roots[i + 1];iroots[i] = iroots[i + 1] * iroots[i + 1];}mint prod = 1, iprod = 1;for(int i = 0; i <= max_base - 3; i++){rate3[i] = roots[i + 3] * prod;irate3[i] = iroots[i + 3] * iprod;prod *= iroots[i + 3];iprod *= roots[i + 3];}}static void ntt(vector<mint> &A){init();int n = A.size();int h = __builtin_ctz(n);int le = 0;mint imag = roots[2];if(h & 1){int p = 1 << (h - 1);for(int i = 0; i < p; i++){auto r = A[i + p];A[i + p] = A[i] - r;A[i] += r;}le++;}for(; le + 1 < h; le += 2){int p = 1 << (h - le - 2);for(int i = 0; i < p; i++){auto a0 = A[i];auto a1 = A[i + p];auto a2 = A[i + 2 * p];auto a3 = A[i + 3 * p];auto a1na3imag = (a1 - a3) * imag;A[i] = a0 + a2 + a1 + a3;A[i + p] = a0 + a2 - (a1 + a3);A[i + 2 * p] = a0 - a2 + a1na3imag;A[i + 3 * p] = a0 - a2 - a1na3imag;}mint rot = rate3[0];for(int s = 1; s < (1 << le); s++){int offset = s << (h - le);mint rot2 = rot * rot;mint rot3 = rot2 * rot;for(int i = 0; i < p; i++){auto a0 = A[i + offset];auto a1 = A[i + offset + p] * rot;auto a2 = A[i + offset + 2 * p] * rot2;auto a3 = A[i + offset + 3 * p] * rot3;auto a1na3imag = (a1 - a3) * imag;A[i + offset] = a0 + a2 + a1 + a3;A[i + offset + p] = a0 + a2 - (a1 + a3);A[i + offset + 2 * p] = a0 - a2 + a1na3imag;A[i + offset + 3 * p] = a0 - a2 - a1na3imag;}rot *= rate3[__builtin_ctz(~s)];}}}static void intt(vector<mint> &A, bool f=true){init();int n = A.size();int h = __builtin_ctz(n);int le = h;mint iimag = iroots[2];for(; le > 1; le -= 2){int p = 1 << (h - le);for(int i = 0; i < p; i++){auto a0 = A[i];auto a1 = A[i + p];auto a2 = A[i + 2 * p];auto a3 = A[i + 3 * p];auto a2na3iimag = (a2 - a3) * iimag;A[i] = a0 + a1 + a2 + a3;A[i + p] = a0 - a1 + a2na3iimag;A[i + 2 * p] = a0 + a1 - (a2 + a3);A[i + 3 * p] = a0 - a1 - a2na3iimag;}mint irot = irate3[0];for(int s = 1; s < (1 << (le - 2)); s++){int offset = s << (h - le + 2);mint irot2 = irot * irot;mint irot3 = irot2 * irot;for(int i = 0; i < p; i++){auto a0 = A[i + offset];auto a1 = A[i + offset + p];auto a2 = A[i + offset + 2 * p];auto a3 = A[i + offset + 3 * p];auto a2na3iimag = (a2 - a3) * iimag;A[i + offset] = a0 + a1 + a2 + a3;A[i + offset + p] = (a0 - a1 + a2na3iimag) * irot;A[i + offset + 2 * p] = (a0 + a1 - (a2 + a3)) * irot2;A[i + offset + 3 * p] = (a0 - a1 - a2na3iimag) * irot3;}irot *= irate3[__builtin_ctz(~s)];}}if(le >= 1){int p = 1 << (h - 1);for(int i = 0; i < p; i++){auto ajp = A[i] - A[i + p];A[i] += A[i + p];A[i + p] = ajp;}}if(f){mint inv = mint(1) / n;for(int i = 0; i < n; i++){A[i] *= inv;}}}static vector<mint> multiply(vector<mint> A, vector<mint> B){int need = A.size() + B.size() - 1;if(min(A.size(), B.size()) < 60){vector<mint> C(need, 0);for(int i = 0; i < A.size(); i++) for(int j = 0; j < B.size(); j++){C[i + j] += A[i] * B[j];}return C;}int sz = 1;while(sz < need) sz <<= 1;A.resize(sz, 0);B.resize(sz, 0);ntt(A);ntt(B);mint inv = mint(1) / sz;for(int i = 0; i < sz; i++) A[i] *= B[i] * inv;intt(A, false);A.resize(need);return A;}};template<typename mint>vector<mint> NumberTheoreticTransform<mint>::roots = vector<mint>();template<typename mint>vector<mint> NumberTheoreticTransform<mint>::iroots = vector<mint>();template<typename mint>vector<mint> NumberTheoreticTransform<mint>::rate3 = vector<mint>();template<typename mint>vector<mint> NumberTheoreticTransform<mint>::irate3 = vector<mint>();template<typename mint>int NumberTheoreticTransform< mint >::max_base = 0;#line 191 "A.cpp"using NTT = NumberTheoreticTransform<mint>;void solve(){INT(n);LL(b, c);Combination<mint> Comb(n + 10);if(c > b){print(0);return;}vec(mint, dp, n + 1, 0);dp[0] = 1;vec(mint, odd, n + 1, 0);vec(mint, even, n + 1, 0);fori(i, n + 1){if(i % 2 == 0) even[i] = Comb.nCk(n, i);else odd[i] = Comb.nCk(n, i);}reverse(all(odd));reverse(all(even));fori(i, 59, -1, -1){dp.resize(2 * n - 1);fori(i, 2 * n - 1, 0, -1){if(i % 2 == 0) dp[i] = dp[i / 2];else dp[i] = 0;}if((b >> i) & 1){vector<mint> ndp(dp.size() + 1);ndp[0] = 0;copy(all(dp), ndp.begin() + 1);swap(dp, ndp);}vector<mint> ndp(n + 1, 0);if((c >> i) & 1){auto res = NTT::multiply(dp, odd);fori(i, n + 1){ndp[i] += res[n + i];}}else{auto res = NTT::multiply(dp, even);fori(i, n + 1){ndp[i] += res[n + i];}}swap(dp, ndp);}print(dp[0]);}int main(){cin.tie(0)->sync_with_stdio(0);// cout << fixed << setprecision(12);int t;t = 1;// cin >> t;while(t--) solve();return 0;}