結果
問題 |
No.2990 Interval XOR
|
ユーザー |
|
提出日時 | 2025-04-20 03:17:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 457 ms / 2,000 ms |
コード長 | 12,128 bytes |
コンパイル時間 | 1,682 ms |
コンパイル使用メモリ | 148,168 KB |
実行使用メモリ | 17,168 KB |
最終ジャッジ日時 | 2025-04-20 03:17:54 |
合計ジャッジ時間 | 9,658 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘void FileIO::setIn(str)’: main.cpp:246:28: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 246 | void setIn(str s) { freopen(s.c_str(), "r", stdin); } | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~ main.cpp: In function ‘void FileIO::setOut(str)’: main.cpp:247:29: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 247 | void setOut(str s) { freopen(s.c_str(), "w", stdout); } | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <vector> using namespace std; using ll = long long; using db = long double; // or double, if TL is tight using str = string; // yay python! // pairs using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<db, db>; #define mp make_pair #define f first #define s second #define tcT template <class T #define tcTU tcT, class U // ^ lol this makes everything look weird but I'll try it tcT > using V = vector<T>; tcT, size_t SZ > using AR = array<T, SZ>; using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<db>; using vs = V<str>; using vpi = V<pi>; using vpl = V<pl>; using vpd = V<pd>; // vectors #define sz(x) int(size(x)) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) rbegin(x), rend(x) #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound tcT > int lwb(const V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); } tcT > int upb(const V<T> &a, const T &b) { return int(ub(all(a), b) - bg(a)); } // loops #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i) #define R0F(i, a) ROF(i, 0, a) #define rep(a) F0R(_, a) #define each(a, x) for (auto &a : x) const int MOD = 998244353; // 1e9+7; const int MX = (int)2e5 + 5; const ll BIG = 1e18; // not too close to LLONG_MAX const db PI = acos((db)-1); const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // for every grid problem!! mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; // bitwise ops // also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until // USACO updates ... return x == 0 ? 0 : 31 - __builtin_clz(x); } // floor(log2(x)) constexpr int p2(int x) { return 1 << x; } constexpr int msk2(int x) { return p2(x) - 1; } ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down tcT > bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) tcT > bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } // set a = max(a,b) tcTU > T fstTrue(T lo, T hi, U f) { ++hi; assert(lo <= hi); // assuming f is increasing while (lo < hi) { // find first index such that f is true T mid = lo + (hi - lo) / 2; f(mid) ? hi = mid : lo = mid + 1; } return lo; } tcTU > T lstTrue(T lo, T hi, U f) { --lo; assert(lo <= hi); // assuming f is decreasing while (lo < hi) { // find first index such that f is true T mid = lo + (hi - lo + 1) / 2; f(mid) ? lo = mid : hi = mid - 1; } return lo; } tcT > void remDup(vector<T> &v) { // sort and remove duplicates sort(all(v)); v.erase(unique(all(v)), end(v)); } tcTU > void safeErase(T &t, const U &u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); } inline namespace IO { #define SFINAE(x, ...) \ template <class, class = void> struct x : std::false_type {}; \ template <class T> struct x<T, std::void_t<__VA_ARGS__>> : std::true_type {} SFINAE(DefaultI, decltype(std::cin >> std::declval<T &>())); SFINAE(DefaultO, decltype(std::cout << std::declval<T &>())); SFINAE(IsTuple, typename std::tuple_size<T>::type); SFINAE(Iterable, decltype(std::begin(std::declval<T>()))); template <auto &is> struct Reader { template <class T> void Impl(T &t) { if constexpr (DefaultI<T>::value) is >> t; else if constexpr (Iterable<T>::value) { for (auto &x : t) Impl(x); } else if constexpr (IsTuple<T>::value) { std::apply([this](auto &...args) { (Impl(args), ...); }, t); } else static_assert(IsTuple<T>::value, "No matching type for read"); } template <class... Ts> void read(Ts &...ts) { ((Impl(ts)), ...); } }; template <class... Ts> void re(Ts &...ts) { Reader<cin>{}.read(ts...); } #define def(t, args...) \ t args; \ re(args); template <auto &os, bool debug, bool print_nd> struct Writer { string comma() const { return debug ? "," : ""; } template <class T> constexpr char Space(const T &) const { return print_nd && (Iterable<T>::value or IsTuple<T>::value) ? '\n' : ' '; } template <class T> void Impl(T const &t) const { if constexpr (DefaultO<T>::value) os << t; else if constexpr (Iterable<T>::value) { if (debug) os << '{'; int i = 0; for (auto &&x : t) ((i++) ? (os << comma() << Space(x), Impl(x)) : Impl(x)); if (debug) os << '}'; } else if constexpr (IsTuple<T>::value) { if (debug) os << '('; std::apply( [this](auto const &...args) { int i = 0; (((i++) ? (os << comma() << " ", Impl(args)) : Impl(args)), ...); }, t); if (debug) os << ')'; } else static_assert(IsTuple<T>::value, "No matching type for print"); } template <class T> void ImplWrapper(T const &t) const { if (debug) os << "\033[0;31m"; Impl(t); if (debug) os << "\033[0m"; } template <class... Ts> void print(Ts const &...ts) const { ((Impl(ts)), ...); } template <class F, class... Ts> void print_with_sep(const std::string &sep, F const &f, Ts const &...ts) const { ImplWrapper(f), ((os << sep, ImplWrapper(ts)), ...), os << '\n'; } void print_with_sep(const std::string &) const { os << '\n'; } }; template <class... Ts> void pr(Ts const &...ts) { Writer<cout, false, true>{}.print(ts...); } template <class... Ts> void ps(Ts const &...ts) { Writer<cout, false, true>{}.print_with_sep(" ", ts...); } } // namespace IO inline namespace Debug { template <typename... Args> void err(Args... args) { Writer<cerr, true, false>{}.print_with_sep(" | ", args...); } template <typename... Args> void errn(Args... args) { Writer<cerr, true, true>{}.print_with_sep(" | ", args...); } void err_prefix(str func, int line, string args) { cerr << "\033[0;31m\u001b[1mDEBUG\033[0m" << " | " << "\u001b[34m" << func << "\033[0m" << ":" << "\u001b[34m" << line << "\033[0m" << " - " << "[" << args << "] = "; } #ifdef LOCAL #define dbg(args...) err_prefix(__FUNCTION__, __LINE__, #args), err(args) #define dbgn(args...) err_prefix(__FUNCTION__, __LINE__, #args), errn(args) #else #define dbg(...) #define dbgn(args...) #endif const auto beg_time = std::chrono::high_resolution_clock::now(); // https://stackoverflow.com/questions/47980498/accurate-c-c-clock-on-a-multi-core-processor-with-auto-overclock?noredirect=1&lq=1 double time_elapsed() { return chrono::duration<double>(std::chrono::high_resolution_clock::now() - beg_time) .count(); } } // namespace Debug inline namespace FileIO { void setIn(str s) { freopen(s.c_str(), "r", stdin); } void setOut(str s) { freopen(s.c_str(), "w", stdout); } void setIO(str s = "") { cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams cout << fixed << setprecision(12); // cin.exceptions(cin.failbit); // throws exception when do smth illegal // ex. try to read letter into int if (sz(s)) setIn(s + ".in"), setOut(s + ".out"); // for old USACO } } // namespace FileIO // make sure to intialize ALL GLOBAL VARS between tcs! /** * Description: modular arithmetic operations * Source: * KACTL * https://codeforces.com/blog/entry/63903 * https://codeforces.com/contest/1261/submission/65632855 (tourist) * https://codeforces.com/contest/1264/submission/66344993 (ksun) * also see https://github.com/ecnerwala/cp-book/blob/master/src/modnum.hpp * (ecnerwal) Verification: https://open.kattis.com/problems/modulararithmetic */ template <int MOD, int RT> struct mint { static const int mod = MOD; static constexpr mint rt() { return RT; } // primitive root for FFT int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int mint() : v(0) {} mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; } bool operator==(const mint &o) const { return v == o.v; } friend bool operator!=(const mint &a, const mint &b) { return !(a == b); } friend bool operator<(const mint &a, const mint &b) { return a.v < b.v; } friend istream &operator>>(istream &is, mint &a) { ll x; is >> x; a = mint(x); return is; } friend ostream &operator<<(ostream &os, mint a) { os << int(a); return os; } mint &operator+=(const mint &o) { if ((v += o.v) >= MOD) v -= MOD; return *this; } mint &operator-=(const mint &o) { if ((v -= o.v) < 0) v += MOD; return *this; } mint &operator*=(const mint &o) { v = int((ll)v * o.v % MOD); return *this; } mint &operator/=(const mint &o) { return (*this) *= inv(o); } friend mint pow(mint a, ll p) { mint ans = 1; assert(p >= 0); for (; p; p /= 2, a *= a) if (p & 1) ans *= a; return ans; } friend mint inv(const mint &a) { assert(a.v != 0); return pow(a, MOD - 2); } mint operator-() const { return mint(-v); } mint &operator++() { return *this += 1; } mint &operator--() { return *this -= 1; } friend mint operator+(mint a, const mint &b) { return a += b; } friend mint operator-(mint a, const mint &b) { return a -= b; } friend mint operator*(mint a, const mint &b) { return a *= b; } friend mint operator/(mint a, const mint &b) { return a /= b; } }; using mi = mint<MOD, 5>; // 5 is primitive root for both common mods using vmi = V<mi>; using pmi = pair<mi, mi>; using vpmi = V<pmi>; V<vmi> scmb; // small combinations void genComb(int SZ) { scmb.assign(SZ, vmi(SZ)); scmb[0][0] = 1; FOR(i, 1, SZ) F0R(j, i + 1) scmb[i][j] = scmb[i - 1][j] + (j ? scmb[i - 1][j - 1] : 0); } pmi operator*(pair<mi, mi> l, pair<mi, mi> r) { return {l.f * r.f, l.s * r.s}; } void operator*=(pair<mi, mi> &l, const pair<mi, mi> &r) { l = l * r; } pmi swap_entries(pair<mi, mi> l) { return {l.s, l.f}; } void solve(int tc) { def(int, M, N); vpi ivals(N); re(ivals); for (auto &[l, r] : ivals) ++r; vmi xo(1 << M); xo.ft = 1; for (auto [l, r] : ivals) xo.ft *= r - l; // dbg(xo.ft); // exit(0); F0R(botbit, M) { int tot_xo = 0; const int B = (M - botbit - 1); V<pair<mi, mi>> dp(1 << B, {1, 1}); for (auto [l, r] : ivals) { int q = 1 << (botbit + 1); int lf = l / q, rf = r / q; int a = l % q, b = r % q; a = min(a, q - a); b = min(b, q - b); tot_xo ^= lf; dp.at((lf ^ rf) & ((1 << B) - 1)) *= {b - a, -b - a}; } F0R(b, B) F0R(i, 1 << B) if (i & (1 << b)) { int ni = i ^ (1 << b); tie(dp.at(ni), dp.at(i)) = mp(dp[ni] * dp[i], dp[ni] * swap_entries(dp[i])); } F0R(i, 1 << B) { xo.at((i << (botbit + 1)) + (1 << botbit)) = dp.at(i).f * (pct(tot_xo & i) & 1 ? -1 : 1); } } F0R(b, M) F0R(i, 1 << M) if (i & (1 << b)) { int ni = i ^ (1 << b); tie(xo.at(ni), xo.at(i)) = mp(xo[ni] + xo[i], xo[ni] - xo[i]); } vmi f; int ans = 0; F0R(i, 1 << M) { f.pb(xo.at(i) / (1 << M)); ps(f.bk); // mi g = f.at(i) * pow(mi(2), i); // ans ^= g.v; } // ps(ans); // dbg(f); // dbg(xo); } int main() { setIO(); int TC = 1; solve(1); // int TC; // re(TC); // FOR(i, 1, TC + 1) solve(i); } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */