Записи в блоге

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Hi,as you see,this is a idea sharing,so if i made mistake please feel free to teach me,i will apprecaite.

1.Counting bits

Observation:From my experience,when you need to get a maximize/minimize/optimize/special pattern with some criterion/function there is high probability related to dp because most of this kind problem belong to np problem. Solution:Digit dp
Time complexity:$$$O(logN)$$$

Ac code

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
using namespace std;
using ll = long long;
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define vc vector
 
constexpr ll mxN=62;
ll n,dp[mxN][2][2];
ll msb(ll x){forr(i,mxN,0)if(x&(1LL<<i)) return i; return -1;}
ll dfs(ll len,ll tight){
	if(!len){
		dp[len][tight][0]=0;
		dp[len][tight][1]=1;
		return dp[len][tight][0];
	}
	if(dp[len][tight][0]!=-1) return dp[len][tight][0];
	dp[len][tight][0]=dp[len][tight][1]=0;
	ll up; up=tight?((n>>(len-1))&1):1;
	forn(i,0,up+1){
		dp[len][tight][0]+=dfs(len-1,tight&(i>=up))+i*dp[len-1][tight&(i>=up)][1];
		dp[len][tight][1]+=dp[len-1][tight&(i>=up)][1];
	}
	return dp[len][tight][0];
}
void solve(istream&cin){
	cin>>n;
	memset(dp,-1,sizeof(dp));
	cout << dfs(msb(n)+1,1) << '\n';
}
int main()
{
	cin.tie(0),ios::sync_with_stdio(false);
	//ifstream cin("input.txt");
	solve(cin);
	return 0;
}

2.Maximum xor subarray

Observation:Let us forget the maximum,if i give a number x i want you to check is that any subarray with xor sum equal to x,how do you do?
You can use Trie,addional Trie supported maximum xor query,consider a problem,if you have a sequance a,a[1],a[2],...,a[n],**Trie** can tell you which two element a[i] and a[j] such that $$$a[i] \oplus a[j]$$$ is the maximum/minimum,so idea is similar at here any subarray xor sum can be obtained by $$$prefix[i] \oplus prefix[j]$$$,here prefix[i] denoted $$$a[1] \oplus a[2] \oplus ... \oplus a[i]$$$,so the problem is how to you find the maximum of two element in the prefix array,prefix[1],prefix[2],...,prefix[n]
Time complexity:$$$O(NlogN)$$$

Ac code

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
using namespace std;
using ll = long long;
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define vc vector
 
constexpr ll mxN=2e5+1;
ll t[mxN*32][2],n,sz;
void insert(ll x){
	ll v; v=0;
	forr(i,30,0){
		if(t[v][(x>>i)&1]==-1) t[v][(x>>i)&1]=++sz;
		v=t[v][(x>>i)&1];
	}
}
ll query(ll x){
	ll v,ans; v=ans=0;
	forr(i,30,0){
		if(t[v][(x>>i)&1^1]!=-1) ans+=(1<<i),v=t[v][(x>>i)&1^1];
		else v=t[v][(x>>i)&1];
	}
	return ans;
}
void solve(istream&cin){
	cin>>n;
	sz=0;
	memset(t,-1,sizeof(t));
	ll pfx,res; pfx=res=0;
	insert(0);
	forn(i,1,n+1){
		ll x; cin>>x;
		pfx^=x;
		res=max(res,query(pfx));
		insert(pfx);
	}
	cout << res << '\n';
}
int main()
{
	cin.tie(0),ios::sync_with_stdio(false);
	//ifstream cin("input.txt");
	solve(cin);
	return 0;
}

3.Maximum xor subset

Observation:Start from now you are going to learning new thing call xor basis,the idea is come from linear algebra,suppose you are at a vector space,there exist a set of vector such that they can't generate each other with linear combination and they can generate every vector in that vector space,we call this set of vecotr basis vector,if you regard the number as binary representation,then you can get a vector,for example $$$9_2$$$=$$$1001_2$$$ and (1,0,0,1) can be regard as a vector.More detail is hard to explain here so i will put a very nice blog at the reference,you can check for more detail.
The key is assume that the highest bit of the maximum input is d,then we can generate at most d xor basis,we define basis[i] is the number with highest bit is i bit(based 1),then we can generate the answer backward,from highest bit to lowest bit,because high bit always greater than all the lowest bit so we can greedily to pick up the answer backward
Time complexity=$O(NlogN)$

Ac code

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
 
constexpr ll mxN=2e5+1;
constexpr ll mxB=31;
ll n,a[mxN],b[mxB]{};
void built(){
	forn(i,1,n+1){
		ll x; x=a[i];
		forr(j,30,0){
			if((x>>j)&1){
				if(!b[j]){b[j]=x; break;}
				else x^=b[j];
			}
		}
	}
}
void solve(istream &cin){
	cin>>n;
	forn(i,1,n+1) cin>>a[i];
	built();
	ll res; res=0;
	forr(i,30,0){
		if(res>>i&1^1) res^=b[i];
	}
	cout << res << '\n';
}
 
int main()
{
    fast_io;
    // ifstream cin("input.txt");
    ll testcase;
    // cin>>testcase;
    testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

4.Number of subset xors

Observation:As you see after you get the basis vector,then assume that there is k basis vector and k<=d,d is the highest bit of maximum input,then the answer is $$$2^d$$$ why?Because there is only d basis vector,xor of any subset of the array is actually the xor of subset of basis vector,so any basis vector have 2 option choose or not choose so answer is $$$2^d$$$
Time complexity=$O(NlogN)$

Ac code

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
 
constexpr ll mxN=2e5+1;
constexpr ll mxB=31;
ll n,a[mxN],b[mxB]{},res=0;
void built(){
	forn(i,1,n+1){
		ll x; x=a[i];
		forr(j,30,0){
			if((x>>j)&1){
				if(!b[j]){b[j]=x,res++; break;}
				else x^=b[j];
			}
		}
	}
}
void solve(istream &cin){
	cin>>n;
	forn(i,1,n+1) cin>>a[i];
	built();
	cout << (1<<res) << '\n';
}
 
int main()
{
    fast_io;
    // ifstream cin("input.txt");
    ll testcase;
    // cin>>testcase;
    testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

5.K subset xors

Observation:Idea is same as previous,first construct the basis vector,then we know there is k basis vector and k<=d,d is the highest bit of maximum input,and the key is in the previous question problem 4,we know the number of subset xor is $$$2^d$$$ this mean that we can just use d number to construct any possible xor of the subset of array,and assume that we have n number in the original array,then there is n-d number is useless,or we can say that after we use d basis vector to construct any possible xor from the subset of array,there is another $$$2^{n-d}$$$ ways to make the xor result become another number,in otherword the $$$2^{n-d}$$$ number $$$\oplus$$$ with the useless $$$n-m$$$ number will form the original number,let look a example,let $$$x$$$ be the number generate by basis vector,then assume that $$$m$$$ is the useless number (not basis vector then become useless) then let $$$x \oplus m = y$$$ there is $$$2^{n-d}$$$ of $$$y$$$ and all of these $$$y \oplus$$$ with useless number will return back to $$$x$$$,so x will appear $$$2^{n-d}$$$,so you can construct the number for at most k distinct number from small to large and every number will appear $$$2^{n-d}$$$,you can generate the number by dfs
Time complexity=O$(NlogN)$

Ac code

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
 
constexpr ll mxN=2e5+1;
constexpr ll mxB=31;
ll n,k,a[mxN],b[mxB]{},m=0,mn=inf;
vc<ll> res;
void built(){
	forn(i,1,n+1){
		ll x; x=a[i];
		forr(j,30,0){
			if((x>>j)&1){
				if(!b[j]){b[j]=x,m++,mn=min(mn,j); break;}
				else x^=b[j];
			}
		}
	}
}
void dfs(ll x,ll y,ll i,ll j){
	if(j>=x){
		res.emp(y);
		return ;
	}
	if(b[i]) dfs(x,y,i+1,j<<1),dfs(x,y^b[i],i+1,j<<1);
	else dfs(x,y,i+1,j);
}
void solve(istream &cin){
	cin>>n>>k;
	forn(i,1,n+1) cin>>a[i];
	built();
	ll x; x=(k+(1<<min(19LL,n-m))-1)/(1<<min(19LL,n-m));
	dfs(x,0,0,1);
	sort(all(res));
	for(auto&v:res){
		forn(i,0,1<<min(19LL,n-m)){
			cout << v << ' ',k--;
			if(!k) break;
		}
		if(!k) break;
	}
	cout << '\n';
}
 
int main()
{
    fast_io;
    // ifstream cin("input.txt");
    ll testcase;
    // cin>>testcase;
    testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

6.All subarray Xor

Observation:Thank omega for sharing hints,this problem can be solved by FWT,but i think a little bit overkill,so if you have simpler solution,welcome to share to me,the idea is FWT allowed us to compute $$$C_k=\sum_{i\oplus j=k}:A_i*B_j$$$ in $$$O(NlogN)$$$ so we can first construct a array $$$prefix[i]$$$ which denoted the prefix with xor sum equal to i,then you can do FWT on $$$prefix[i]$$$ and get $$$prefix'[i]$$$ after that you just simply produce dot product between $$$prefix'[i]$$$ and $$$prefix'[i]$$$ then get a final array $$$ans$$$ which $$$ans[i]=prefix'[i]*prefix'[i]$$$ then just simply check is $$$ans[k] \gt 0$$$ then there must be two $$$prefix[i]$$$ and $$$prefix[j]$$$ such that $$$prefix[i] \oplus prefix[j]=k$$$,be careful on $$$k=0$$$ if there is any $$$prefix$$$ with length $$$i$$$ appear more than once than 0 must always exist
Time complexity=$O(NlogN)$

Ac code

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};

constexpr ll mxB=21;
ll a[1<<mxB]{};
void fwt(ll *arr,ll type){
	for(ll k=2;k<(1<<mxB);k<<=1){
		for(ll i=0,m=k>>1;i+m<(1<<mxB);i+=k){
			forn(j,0,m){
				ll x,y; x=arr[i+j],y=arr[i+j+m];
				arr[i+j]=x+y,arr[i+j+m]=x-y;
				if(type) arr[i+j]/=2,arr[i+j+m]/=2;
			}
		}
	}
}
void solve(istream &cin){
	ll n,pfx,mx;
	cin>>n;
	mx=pfx=0;
	a[0]=1;
	forn(i,0,n){
		ll x; cin>>x;
		pfx^=x,a[pfx]++,mx=max(mx,a[pfx]);
	}
	fwt(a,0);
	forn(i,0,1<<mxB) a[i]=a[i]*a[i];
	fwt(a,1);
	ll res; res=0;
	// forn(i,0,17) cout << a[i] << " \n"[i==16];
	forn(i,0,1<<mxB) res+=(!i?mx>1:a[i]>0);
	cout << res << '\n';
	forn(i,0,1<<mxB) if(!i?mx>1:a[i]) cout << i << ' ';  cout << '\n';
}
 
int main()
{
    fast_io;
    // ifstream cin("input.txt");
    ll testcase;
    // cin>>testcase;
    testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

7.Xor pyramid peak

Observation:This is bit+divide and conquer problem,you don't really need to count $$$n*(n+1)/2$$$ block,you just need to count the number $$$a[i]$$$ appear how many times in the last block,but if you make further observation,you will found if the number appear odd times then a[i] will appear one times if appear even number times then a[i] will not appear,why?Because $$$x \oplus x = 0$$$,the key is count the parity of the appear times of $$$a[i]$$$ in the first block,but how?
Actually does this triangle seem familiar?Try to remember when you are in high school there is one thing call pascal triangle,pascal triangle have a property which is $$$C_{i+1}^{n+1}=C_{i}^n+C_{i+1}^n$$$,this can be explain by dp mindset,imagine you have n+1 stone,i want you to choose i of them,first you separate the stone to two group,1st group with n stones,2nd group with 1 stone,then you have 2 option,first choose a stone from 2nd group then choose i-1 stones from 1st group,second choose no stone from 2nd group then choose i stones from 1st group,so this is same to the formula
Now imagine you are going from first row to nth row,the number of times appear is the ways to the top,assume that you are currently located at a[i] (0 based) now you need to go to first row,how many step you need to go up?n-1 steps,no matter you go top left or top right,you need exactly n-1 steps to reach the top,and try to make further observation,you will find you can do at most i step go to top left(0 based),so the ways is $$$C_i^{n-1}$$$ but remember we need to count the parity which is $$$C_i^{n-1} mod 2$$$,you can't do this by using combination formula because you need to count the inversion and the inversion may be $$$0$$$ mod $$$2$$$ so you need a theorem call lucas theorem,more detail you can check from google,i just say the key,in this problem p=2,and lucas theorem say that if under p numeral system ,there is some $$$n_i$$$ and $$$m_i$$$ such that $$$m_i \gt n_i$$$ then $$$C_n^m$$$ mod $$$p$$$ is equal to zero,this imply if m is not the subset of n then the parity of $$$C_n^m$$$ mod $$$2$$$ is zero,so just check the $$$C_i^n$$$ for every a[i] if i is the subset of n then count the a[i] else not.
Time complexity=$O(N)$

Ac code

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
 
constexpr ll mxB=20;
void solve(istream &cin){
	ll n,res;
	cin>>n;
	res=0;
	forn(i,0,n){
		ll x; cin>>x;
		res^=((i&(n-1))==i)*x;
	}
	cout << res << '\n';
}
 
int main()
{
    fast_io;
    // ifstream cin("input.txt");
    ll testcase;
    // cin>>testcase;
    testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

8.Xor pyramid diagonal

Observation:From the previous problem we have a idea,assume that count from bottom to top,the parity of element a[i](0 based) in the block of the xth row(based 0) is $$$C_i^x$$$ mod $$$2$$$ and the answer of $$$C_i^x$$$ to be $$$1$$$ if and only if i is the subset of x(a is the subset of b if and only if $$$x & y==x$$$),so this reduce to a sos dp problem right?Assume the diagonal from bottom to top,the $$$j$$$ diagonal element denoted $$$b[j]$$$,then $$$b[j]=\oplus_{i\subseteq j}\;a[i]$$$,so the rest is sos dp,you can find a lot of tutorial about it and i believe they are explain better than me.
Time complexity=$O(NlogN)$

Ac code

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
 
constexpr ll mxB=20;
void solve(istream &cin){
	ll n;
	cin>>n;
	vc<ll> dp(n);
	forn(i,0,n) cin>>dp[i];
	forn(i,0,mxB){
		forn(j,0,n){
			if((j>>i)&1) dp[j]^=dp[j^(1<<i)];
		}
	}
	forn(i,0,n) cout << dp[i] << " \n"[i==n-1];
}
 
int main()
{
    fast_io;
    // ifstream cin("input.txt");
    ll testcase;
    // cin>>testcase;
    testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

9.Xor pyramid Row

Observation:This is classic binary lifting problem,we know one fact is for any given number $$$x$$$ it can be represent as the sum of power of 2,and for a power of 2 there is only not subset which itself and 0,for example $$$2^3=1000_2$$$ obviously there is only one 1's in the number so there is only two subset,in otherword assume that the number of row be $$$i$$$ and index of the element is $$$j$$$ and $$$dp[i][j]$$$ denoted the element at $$$2^i$$$ row from the bottom and $$$j:th$$$ from left to right,then obviously $$$dp[i][j]=dp[0][j]+dp[0][j+2^i]$$$,$$$dp[0][j]$$$ is the element of the input array,so for a given $$$n$$$ it atmost $$$logN$$$ bit and for every time construct we need at most $$$O(N)$$$,so we can do a binary lifting in $$$O(NlogN)$$$
Time complexity=$O(NlogN)$

Ac code

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
 
constexpr ll mxB=20;
void solve(istream &cin){
	ll n,k;
	cin>>n>>k;
	vc<ll> a(n);
	for(auto&v:a) cin>>v;
	k=n-k;
	forn(i,0,mxB){
		if(k&(1<<i)){
			forn(j,0,n-(1<<i)){
				a[j]=a[j]^a[j+(1<<i)];
			}
		}
	}
	forn(i,0,n-k) cout << a[i] << " \n"[i==n-k-1];
}
 
int main()
{
    fast_io;
    // ifstream cin("input.txt");
    ll testcase;
    // cin>>testcase;
    testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

10.SOS bit problem

Observation:As you can see the problem name is sos bit problem.I just sharing some key idea,d?For $$$x|y=x$$$,in otherword if $$$k:th$$$ bit of x is closed the $$$k:th$$$ bit of y should also be closed,in otherword this mean y is the subset of x.How about $$$x & y=x$$$?I belive most of you already feeling that x should be subset of y because we look at $$$k:th$$$ bit of x if is open then in y it also should be open but if it's closed but in y maybe open or closed to x is the subset of y or we say that y is the superset of x,so also be solve in sos dp.At the last $$$x & y:!=0$$$,you can just flip x from 0 to 1 and 1 to 0 then this number is the only number such that it $$$\oplus x=0$$$
Time complexity=$O(NLogN)$

Ac code

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
 
constexpr ll mxX=1e6+1;
constexpr ll mxB=20;
constexpr ll mxN=2e5+1;
ll n,a[mxN],dp[1<<mxB][2]={0};
void solve(istream &cin){
	cin>>n;
	forn(i,1,n+1){
		cin>>a[i];
		dp[a[i]][0]++,dp[a[i]][1]++;
		// if((~a[i])<=mxX) dp[~a[i]][1]++;
	}
	forn(j,0,mxB){
		forn(i,1,(1<<mxB)){
			if((i>>j)&1) dp[i][0]+=dp[i^(1<<j)][0];
			if(!((i>>j)&1) && (i^(1<<j))<(1<<mxB)) dp[i][1]+=dp[i^(1<<j)][1];
		}
	}
	forn(i,1,n+1){
		cout << dp[a[i]][0] << ' ' << dp[a[i]][1] << ' ' << n-dp[(~a[i])&((1<<mxB)-1)][0] << '\n';
	}
}
 
int main()
{
    fast_io;
    // ifstream cin("input.txt");
    ll testcase;
    // cin>>testcase;
    testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

11.And subset count

Observation:This one is also sos dp problem,the key is same as the previous,we separate two part to do,first we find all the number $$$y$$$ such that $$$x\subset y$$$ we denoted as $$$dp[x]$$$ and then there is $$$2^{dp[x]}-1$$$ ways,the logic is straight forward,there is $$$dp[x]$$$ element is the superset of $$$x$$$ in otherword if $$$i & j \gt =x$$$ then $$$i,j \subset dp[x]$$$ otherwise you can't get $$$x$$$,but in $$$2^{dp[x]}-1$$$ there is some invalid answer which is it greater than $$$x$$$ so we need to substract it.
Time complexity=$O(NlogN)$

Ac code

/*--------------\
/   author :tlx   \
\      Tylee      /
 \--------------*/
//Ying with me
#include<iostream>
#include<bitset>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<array>
#include<functional>
#include<iterator>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
using ii=int;
using ll=long long;
using ull=unsigned long long;
#define DEBUG 1 
#if DEBUG
    #define err(...) cerr << '[' << #__VA_ARGS__ << "] = "; debug(__VA_ARGS__)
    template<typename T,typename... Args>
    inline void debug (const T& val,const Args&... args){
        cerr << '[' << val; ((cerr << ' ' << args),...); cerr << "]\n";
    }
    #define terr cerr << "I am here" << '\n'
#endif
#define fast_io cin.tie(0),ios::sync_with_stdio(false)
#define forn(a,b,c) for(ll a=b;a<c;++a)
#define forr(a,b,c) for(ll a=b;a>=c;--a)
#define all(name) name.begin(),name.end()
#define allb(name) name.begin(),name.begin()
#define ps push
#define emp emplace_back
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define vc vector
#define ar array
#define uno unordered_map
#define uns unordered_set
#define pr pair
#define pii pr<ii,ii>
#define pll pr<ll,ll>
#define prq priority_queue
#define mls multiset
#define rbg rbegin
#define bg begin
#define ed end
#define fr first
#define sc second
constexpr ll mdl1=1e9+7;
constexpr ll mdl2=998244353;
constexpr ll finv=(mdl1+1)/2;
constexpr ll inf=1e18;
 
//0=L 1=D 2=R 3=U
//ll dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
//0=L 1=LD 2=D 3=RD 4=R 5=RU 6=U 7=LU
// ll dy[8]={-1,-1,0,1,1,1,0,-1},dx[8]={0,1,1,1,0,-1,-1,-1};
 
constexpr ll mxN=2e5+1;
constexpr ll mxB=20;
ll n,dp[1<<mxB]{},p2[mxN];
void solve(istream &cin){
	cin>>n;
	p2[0]=1;
	forn(i,1,mxN) p2[i]=(p2[i-1]*2)%mdl1;
	forn(i,1,n+1){
		ll x; cin>>x;
		dp[x]++;
	}
	forn(i,0,mxB){
		forn(j,0,1<<mxB){
			if((j>>i)&1^1) dp[j]=(dp[j]+dp[j|(1<<i)])%mdl1;
		}
	}
	forn(i,0,1<<mxB) dp[i]=p2[dp[i]]-1;
	forn(i,0,mxB){
		forn(j,0,1<<mxB){
			if((j>>i)&1^1) dp[j]=(dp[j]-dp[j|(1<<i)])%mdl1;
		}
	}
	forn(i,0,n+1) cout << ((dp[i]%mdl1)+mdl1)%mdl1 << " \n"[i==n];
}
 
int main()
{
    fast_io;
    // ifstream cin("input.txt");
    ll testcase;
    // cin>>testcase;
    testcase=1;
    while(testcase--)
        solve(cin);
    return 0;
}

Полный текст и комментарии »

Блог пользователя rubbish

1.Counting bits

2.Maximum xor subarray

3.Maximum xor subset

4.Number of subset xors

5.K subset xors

6.All subarray Xor

7.Xor pyramid peak

8.Xor pyramid diagonal

9.Xor pyramid Row

10.SOS bit problem

11.And subset count