This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0402 #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../convolution/bitwise/fwht.cpp" #include "../../convolution/bitwise/xor.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; ll n,k; cin>>n>>k; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; const int LOG = 20; const int sz = 1<<LOG; vector<ll> cnt(sz,0); cnt[0]++; for(int i=0,s=0;i<n;i++){ s^=as[i]; cnt[s]++; } fwht(cnt,bitwise_xor::zeta); for(ll &v:cnt) v=v*v; fwht(cnt,bitwise_xor::moebius); k--; for(int v=sz-1;v>=0;v--){ cnt[v]/=2; if(cnt[v]<=k){ k-=cnt[v]; continue; } cout<<v<<endl; break; } return 0; }
#line 1 "test/aoj/0402.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0402 #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "convolution/bitwise/fwht.cpp" #line 3 "convolution/bitwise/fwht.cpp" using namespace std; #endif // https://kazuma8128.hatenablog.com/entry/2018/05/31/144519 //BEGIN CUT HERE // O(n \log n) template<typename T, typename F> void fwht(vector<T> &as,F f){ int n=as.size(); for(int d=1;d<n;d<<=1) for(int m=d<<1,i=0;i<n;i+=m) for(int j=0;j<d;j++) f(as[i+j],as[i+j+d]); } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "convolution/bitwise/xor.cpp" #line 3 "convolution/bitwise/xor.cpp" using namespace std; #endif //BEGIN CUT HERE namespace bitwise_xor{ auto zeta=[](auto& lo,auto& hi){ auto x=lo+hi,y=lo-hi; lo=x; hi=y; }; auto moebius=[](auto& lo,auto& hi){ auto x=lo+hi,y=lo-hi; lo=x/decltype(x)(2); hi=y/decltype(y)(2); }; } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 9 "test/aoj/0402.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; ll n,k; cin>>n>>k; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; const int LOG = 20; const int sz = 1<<LOG; vector<ll> cnt(sz,0); cnt[0]++; for(int i=0,s=0;i<n;i++){ s^=as[i]; cnt[s]++; } fwht(cnt,bitwise_xor::zeta); for(ll &v:cnt) v=v*v; fwht(cnt,bitwise_xor::moebius); k--; for(int v=sz-1;v>=0;v--){ cnt[v]/=2; if(cnt[v]<=k){ k-=cnt[v]; continue; } cout<<v<<endl; break; } return 0; }