結果
問題 |
No.2990 Interval XOR
|
ユーザー |
![]() |
提出日時 | 2025-04-23 02:48:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 253 ms / 2,000 ms |
コード長 | 8,886 bytes |
コンパイル時間 | 4,109 ms |
コンパイル使用メモリ | 286,632 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2025-04-23 02:48:34 |
合計ジャッジ時間 | 13,654 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
// #line 1 "2990.cpp" /* Interval XOR i = (2h+1) * 2^s として 各 s について h \in [0,2^{n-1-s}) についてまとめて解く L = 0 なら p(h & (R>>(s+1))) * (h によらない、区間による部分) の区間に対する積になってできる 一般には p(h & (R>>(s+1))) * c1 + p(h & (L>>(s+1))) * c2 の積 となるので和の積になってやばそうだが、 実は意味なさそうな変形 = p(h & (R>>(s+1))) * (c1 + c2 * p(h & ((R^L)>>(s+1)))) の形ならできる */ // #pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("Ofast") // #line 2 "/home/sigma/comp/library/template.hpp" #include <bits/stdc++.h> using namespace std; using ll = long long; using uint = unsigned int; using ull = unsigned long long; #define rep(i,n) for(int i=0;i<int(n);i++) #define rep1(i,n) for(int i=1;i<=int(n);i++) #define per(i,n) for(int i=int(n)-1;i>=0;i--) #define per1(i,n) for(int i=int(n);i>0;i--) #define all(c) c.begin(),c.end() #define si(x) int(x.size()) #define pb push_back #define eb emplace_back #define fs first #define sc second template<class T> using V = vector<T>; template<class T> using VV = vector<vector<T>>; template<class T,class U> bool chmax(T& x, U y){ if(x<y){ x=y; return true; } return false; } template<class T,class U> bool chmin(T& x, U y){ if(y<x){ x=y; return true; } return false; } template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());} template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();} template<class T> V<T> Vec(size_t a) { return V<T>(a); } template<class T, class... Ts> auto Vec(size_t a, Ts... ts) { return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...)); } template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){ return o<<"("<<p.fs<<","<<p.sc<<")"; } template<typename Tuple, size_t... Is> void print_tuple_impl(ostream& os, const Tuple& tup, index_sequence<Is...>){ ((os << (Is == 0 ? "" : ",") << get<Is>(tup)), ...); } template<typename... Args> std::ostream& operator<<(std::ostream& os, const std::tuple<Args...>& tup) { os << "("; print_tuple_impl(os, tup, std::index_sequence_for<Args...>{}); os << ")"; return os; } template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){ o<<"{"; for(const T& v:vc) o<<v<<","; o<<"}"; return o; } constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); } #ifdef LOCAL const bool DEBUG = true; const bool SUBMIT = false; #define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl void dmpr(ostream& os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" ~ "; dmpr(os,args...); } #define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__) #define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {"; \ for(auto v: x) cerr << v << ","; cerr << "}" << endl; #else const bool DEBUG = false; const bool SUBMIT = true; #define show(x) void(0) #define dump(x) void(0) #define shows(...) void(0) #endif template<class D> D divFloor(D a, D b){ return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0); } template<class D> D divCeil(D a, D b) { return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0); } // #line 1 "/home/sigma/comp/library/math/mint.hpp" template<unsigned int mod_> struct ModInt{ using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr static uint mod = mod_; uint v; ModInt():v(0){} ModInt(ll _v):v(normS(_v%mod+mod)){} explicit operator bool() const {return v!=0;} static uint normS(const uint &x){return (x<mod)?x:x-mod;} // [0 , 2*mod-1] -> [0 , mod-1] static ModInt make(const uint &x){ModInt m; m.v=x; return m;} ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));} ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));} ModInt operator-() const { return make(normS(mod-v)); } ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);} ModInt operator/(const ModInt& b) const { return *this*b.inv();} ModInt& operator+=(const ModInt& b){ return *this=*this+b;} ModInt& operator-=(const ModInt& b){ return *this=*this-b;} ModInt& operator*=(const ModInt& b){ return *this=*this*b;} ModInt& operator/=(const ModInt& b){ return *this=*this/b;} ModInt& operator++(int){ return *this=*this+1;} ModInt& operator--(int){ return *this=*this-1;} template<class T> friend ModInt operator+(T a, const ModInt& b){ return (ModInt(a) += b);} template<class T> friend ModInt operator-(T a, const ModInt& b){ return (ModInt(a) -= b);} template<class T> friend ModInt operator*(T a, const ModInt& b){ return (ModInt(a) *= b);} template<class T> friend ModInt operator/(T a, const ModInt& b){ return (ModInt(a) /= b);} ModInt pow(ll p) const { if(p<0) return inv().pow(-p); ModInt a = 1; ModInt x = *this; while(p){ if(p&1) a *= x; x *= x; p >>= 1; } return a; } ModInt inv() const { // should be prime return pow(mod-2); } bool operator==(const ModInt& b) const { return v==b.v;} bool operator!=(const ModInt& b) const { return v!=b.v;} bool operator<(const ModInt& b) const { return v<b.v;} friend istream& operator>>(istream &i, ModInt& x){ ll v; i >> v; x = ModInt(v); return i; } friend ostream& operator<<(ostream &o, const ModInt& x){ return o<<x.v;} // friend ostream& operator<<(ostream &o,const ModInt& x){ // for(int b=1;b<=1000;b++){ // ModInt ib = ModInt(b).inv(); // for(int a=-1000;a<=1000;a++){ // if(ModInt(a) * ib == x){ // return o << a << "/" << b; // } // } // } // return o<<x.v; // } }; using mint = ModInt<998244353>; //using mint = ModInt<1000000007>; V<mint> fact,ifact,invs; // a,b >= 0 のみ mint Choose(int a,int b){ if(b<0 || a<b) return 0; return fact[a] * ifact[b] * ifact[a-b]; } /* // b >= 0 の範囲で、 Choose(a,b) = a(a-1)..(a-b+1) / b! mint Choose(int a,int b){ if(b<0 || a<b) return 0; return fact[a] * ifact[b] * ifact[a-b]; } */ void InitFact(int N){ //[0,N] N++; fact.resize(N); ifact.resize(N); invs.resize(N); fact[0] = 1; rep1(i,N-1) fact[i] = fact[i-1] * i; ifact[N-1] = fact[N-1].inv(); for(int i=N-2;i>=0;i--) ifact[i] = ifact[i+1] * (i+1); rep1(i,N-1) invs[i] = fact[i-1] * ifact[i]; } // #line 14 "2990.cpp" template<class T> void hadamard(V<T>& a, bool inv = false){ int n = si(a); assert(__builtin_popcount(n) == 1); for(int i=1;i<n;i<<=1){ for(int j=0;j<n;j+=i<<1){ rep(k,i){ T s = a[j+k], t = a[j+k+i]; a[j+k] = s+t; a[j+k+i] = s-t; } } } if(inv){ T in = T(1)/n; for(auto& x: a) x *= in; } } /* c[i] = \sum_j ( p(j & 1) == 1 ? a[i] : b[i] ) 上のコードを実行中の a に入っている値は、入力の a を使って、 + a[] + a[] - a[] - a[] みたいに係数が-1,0,1 のいずれかで書けることがわかる ということは係数が1のa[]の和、-1のa[]の和、を分けて持てば、最終的に + なものの和と - なものの和がわかる T は逆元すら仮定せず可換モノイドでよい 不思議かも 今回は T = (mint, *) なので直接書いています */ template<class T> vector<T> hadamard2(const vector<T>& a, const vector<T>& b){ assert(a.size() == b.size()); int n = si(a); assert(__builtin_popcount(n) == 1); vector<pair<T,T>> c(n); rep(i,n) c[i] = {a[i], b[i]}; for(int i=1;i<n;i<<=1){ for(int j=0;j<n;j+=i<<1){ rep(k,i){ auto s = c[j+k], t = c[j+k+i]; c[j+k] = {s.fs*t.fs, s.sc*t.sc}; c[j+k+i] = {s.fs*t.sc, s.sc*t.fs}; } } } vector<T> res(n); rep(i,n) res[i] = c[i].fs; return res; } int main(){ cin.tie(0); ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !! cout << fixed << setprecision(20); int N,M; cin >> N >> M; vector<pair<int,int>> seg(M); rep(i,M) cin >> seg[i].fs >> seg[i].sc, seg[i].sc++; /* f[i] = 各区間 [L,R) を hadamard 変換した時の [i] の各点積 = \prod_{区間} \sum_{L <= j < R} p(j & i) */ V<mint> f(1<<N); { // i = 0 f[0] = 1; for(auto [L,R] : seg) f[0] *= R-L; } rep(s,N){ // i = (2h+1) * 2^s for h in [0,2^{N-1-s}) const int mask = (1<<(s+1)) - 1; const int H = 1 << (N-1-s); V<mint> a(H,1), b(H,1); for(auto [L,R] : seg){ /* \sum_{L <= j < R} p(j & (2h+1) * 2^s) = p(h & r) * c1 + p(h & l) * c2 = p(h & r) * (c1 + c2 * p(h & (r^l))) */ int r = R >> (s+1), l = L >> (s+1); if(r == H) r = 0; int rm = R & mask, lm = L & mask; mint c1 = min(rm,(1<<(s+1))-rm), c2 = -min(lm,(1<<(s+1))-lm); a[r] *= 1; b[r] *= -1; a[r^l] *= c1 + c2; b[r^l] *= c1 - c2; } auto c = hadamard2(a,b); rep(h,H) f[(2*h+1) << s] = c[h]; } hadamard(f); mint ip2 = mint(2).pow(-N); for(auto& v: f) cout << v * ip2 << '\n'; }