結果
問題 |
No.2990 Interval XOR
|
ユーザー |
|
提出日時 | 2025-08-16 23:10:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 9,848 bytes |
コンパイル時間 | 3,555 ms |
コンパイル使用メモリ | 294,648 KB |
実行使用メモリ | 58,076 KB |
最終ジャッジ日時 | 2025-08-16 23:10:35 |
合計ジャッジ時間 | 19,984 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | AC * 3 WA * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define all(a) begin(a), end(a) #define rall(a) rbegin(a), rend(a) #define len(a) (int)((a).size()) /* ! WARNING: MOD must be prime if you use division or .inv(). ! WARNING: 2 * (MOD - 1) must be smaller than INT_MAX * Use .value to get the stored value. */ template<typename T> int normalize(T value, int mod) { if (value < -mod || value >= 2 * mod) value %= mod; if (value < 0) value += mod; if (value >= mod) value -= mod; return value; } template<int mod> struct static_modular_int { static_assert(mod - 2 <= std::numeric_limits<int>::max() - mod, "2(mod - 1) <= INT_MAX"); using mint = static_modular_int<mod>; int value; static_modular_int() : value(0) {} static_modular_int(const mint &x) : value(x.value) {} template<typename T, typename U = std::enable_if_t<std::is_integral<T>::value>> static_modular_int(T value) : value(normalize(value, mod)) {} static constexpr int get_mod() { return mod; } template<typename T> mint power(T degree) const { mint prod = 1, a = *this; for (; degree > 0; degree >>= 1, a *= a) if (degree & 1) prod *= a; return prod; } mint inv() const { return power(mod - 2); } mint& operator=(const mint &x) { value = x.value; return *this; } mint& operator+=(const mint &x) { value += x.value; if (value >= mod) value -= mod; return *this; } mint& operator-=(const mint &x) { value -= x.value; if (value < 0) value += mod; return *this; } mint& operator*=(const mint &x) { value = int64_t(value) * x.value % mod; return *this; } mint& operator/=(const mint &x) { return *this *= x.inv(); } friend mint operator+(const mint &x, const mint &y) { return mint(x) += y; } friend mint operator-(const mint &x, const mint &y) { return mint(x) -= y; } friend mint operator*(const mint &x, const mint &y) { return mint(x) *= y; } friend mint operator/(const mint &x, const mint &y) { return mint(x) /= y; } mint& operator++() { ++value; if (value == mod) value = 0; return *this; } mint& operator--() { --value; if (value == -1) value = mod - 1; return *this; } mint operator++(int) { mint prev = *this; value++; if (value == mod) value = 0; return prev; } mint operator--(int) { mint prev = *this; value--; if (value == -1) value = mod - 1; return prev; } mint operator-() const { return mint(0) - *this; } bool operator==(const mint &x) const { return value == x.value; } bool operator!=(const mint &x) const { return value != x.value; } bool operator<(const mint &x) const { return value < x.value; } template<typename T> explicit operator T() { return value; } friend std::istream& operator>>(std::istream &in, mint &x) { std::string s; in >> s; x = 0; bool neg = s[0] == '-'; for (const auto c : s) if (c != '-') x = x * 10 + (c - '0'); if (neg) x *= -1; return in; } friend std::ostream& operator<<(std::ostream &out, const mint &x) { return out << x.value; } static int primitive_root() { if constexpr (mod == 1'000'000'007) return 5; if constexpr (mod == 998'244'353) return 3; if constexpr (mod == 786433) return 10; static int root = -1; if (root != -1) return root; std::vector<int> primes; int value = mod - 1; for (int i = 2; i * i <= value; i++) if (value % i == 0) { primes.push_back(i); while (value % i == 0) value /= i; } if (value != 1) primes.push_back(value); for (int r = 2;; r++) { bool ok = true; for (auto p : primes) if ((mint(r).power((mod - 1) / p)).value == 1) { ok = false; break; } if (ok) return root = r; } } }; // constexpr int MOD = 1'000'000'007; constexpr int MOD = 998'244'353; using mint = static_modular_int<MOD>; vector<mint> adamar(vector<mint> vec) { for (ll bit = 1; bit < len(vec); bit *= 2) { for (int i = 0; i < len(vec); ++i) { if (i & bit) { mint old1 = vec[i], old0 = vec[i - bit]; vec[i] = old0 - old1; vec[i - bit] = old0 + old1; } } } return vec; } vector<mint> forward(vector<pair<int, int>> segs, int m) { struct tup { array<ll, 4> p, c; tup() { p = {0, 0, 0, 0}; c = {0, 0, 0, 0}; } }; struct pr { array<ll, 2> p, c; pr() { p = {0, 0}; c = {0, 0}; } }; vector<mint> vec(1 << m); for (ll bit = 1; bit < len(vec); bit *= 2) { ll mask = (bit * 2 - 1), high = bit; auto push = [&](ll l, ll r, ll ind, tup& p) { if ((l & high) == (r & high)) { p.p[ind] = ((l | (high - 1)) ^ (high - 1)); p.c[ind] = (r - l + 1); return; } ll mid = ((r | (high - 1)) ^ (high - 1)); p.p[ind + 1] = mid; p.c[ind + 1] = r - mid + 1; p.p[ind] = ((l | (high - 1)) ^ (high - 1)); p.c[ind] = mid - l; }; vector<tup> tups(len(segs)); for (int i = 0; auto c : segs) { if (c.second - (c.second & mask) == c.first - (c.first & mask)) { push(c.first, c.second, 0, tups[i]); } else { if ((c.first & mask) != 0) push(c.first, (c.first | mask), 0, tups[i]); if (((c.second + 1) & mask) != 0) push((c.second | mask) ^ mask, c.second, 2, tups[i]); } ++i; } vector<pr> pairs(len(segs)); for (int i = 0; i < len(segs); ++i) { pairs[i].p[0] = tups[i].p[0]; pairs[i].c[0] = tups[i].c[0] - tups[i].c[1]; pairs[i].p[1] = tups[i].p[2]; pairs[i].c[1] = tups[i].c[2] - tups[i].c[3]; } auto do_calc = [](const vector<pr>& pairs, ll bt, ll m) { vector<mint> res(1 << m); vector<array<mint, 2>> sum(1 << m, {1, 1}), diff(1 << m, {1, 1}), par(1 << m, {0, 0}); for (auto c : pairs) { sum[c.p[0] ^ c.p[1]][0] *= (c.c[0] + c.c[1]); diff[c.p[0] ^ c.p[1]][0] *= (c.c[0] - c.c[1]); par[c.p[0]][0] += 1; } for (ll bit = 1; bit < len(res); bit *= 2) { for (int i = 0; i < len(res); i += bt) { if (i & bit) { array<mint, 2> old_sum1 = sum[i], old_sum0 = sum[i - bit], old_diff1 = diff[i], old_diff0 = diff[i - bit], old_par1 = par[i], old_par0 = par[i - bit]; sum[i][0] = old_sum1[1] * old_sum0[0]; sum[i][1] = old_sum1[0] * old_sum0[1]; sum[i - bit][0] = old_sum1[0] * old_sum0[0]; sum[i - bit][1] = old_sum1[1] * old_sum0[1]; diff[i][0] = old_diff1[1] * old_diff0[0]; diff[i][1] = old_diff1[0] * old_diff0[1]; diff[i - bit][0] = old_diff1[0] * old_diff0[0]; diff[i - bit][1] = old_diff1[1] * old_diff0[1]; par[i][0] = old_par1[1] + old_par0[0]; par[i][1] = old_par1[0] + old_par0[1]; par[i - bit][0] = old_par1[0] + old_par0[0]; par[i - bit][1] = old_par1[1] + old_par0[1]; } } } for (int i = 0; i < len(res); i += bt) { res[i] = sum[i][0] * diff[i][1]; if (par[i][1].value % 2) res[i] *= mint(-1); } return res; }; vector<mint> res = do_calc(pairs, bit, m); for (int i = 0; i < len(vec); ++i) { if (!(i & bit)) continue; if (i & (bit - 1)) continue; vec[i] = res[i]; } // for (int i = 0; i < len(vec); ++i) { // if (!(i & bit)) continue; // if (i & (bit - 1)) continue; // vec[i] = 1; // for (auto p : pairs) { // mint cur = 0; // for (int t = 0; t < 2; ++t) { // int ppcnt = __builtin_popcount(i & p.p[t]); // mint sgn = (ppcnt % 2) ? -1 : 1; // cur += sgn * p.c[t]; // } // vec[i] *= cur; // } // } } vec[0] = 1; for (auto c : segs) vec[0] *= (c.second - c.first + 1); return vec; } void solve() { int n, m; cin >> n >> m; swap(n, m); vector<pair<int, int>> segs(n); for (auto &c : segs) cin >> c.first >> c.second; vector<mint> to = forward(segs, m); vector<mint> res = adamar(to); for (auto& c : res) c /= len(res); // for (auto c : res) cerr << c << " "; // cerr << endl; ll ans = 0; for (int i = 0; auto c : res) { ans ^= ll(mint(2).power(i) * c); ++i; } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); return 0; }