Educational Codeforces Round 157 (Rated for Div. 2)

F. Fancy Arrays

第一眼感觉是去容斥掉条件 1，因为条件 2 其实挺紧的。

不妨用 \(f(l,r)\) 表示 \(a\) 值域在 \([l,r]\) 的方案（满足条件 2）。

那么答案为 \(f(0,+\infty)-f(0,x-1)-f(x+k,+\infty)\)，因为如果选了 \([0,x-1]\) 的数，那么还要更大的话，一定会选到 \([x,x+k-1]\)，所以你要钦定没有的话，一定只能在 \([0,x-1]\) 里面选。\(>x+k-1\) 同理。

考虑 \(+\infty\) 的上界很烦，能不能合并下消去，\(f(0,+\infty)-f(x+k,+\infty)\) 是啥？显然是存在一个数在 \([0,x+k-1]\) 的方案数。抽象到二维平面上便可以很好的解释。或者考虑二者的集合对称差，显然是 \([0,x+k-1]\) 这意味着二者减去之后一定是存在一个数在 \([0,x+k-1]\) 的方案数。考虑咋做。这个东西等价于最小值在这个区间的方案数，考虑钦定差分数组，接下来，记差分数组的前缀最小值为 \(mi\)，那么最小值显然为 \(a_1+mi\)，考虑钦定 \(a_1+mi\) 落在那个区间即可。而你会发现，我们这样钦定实际上对于差分数组是没有限制的。那这样钦定一定不重不漏吗？考虑一个序列，显然一定会被钦定到。接下来，再考虑一个序列，会被钦定几次？你注意到，对于一种确定的差分数组，其最小值的位置/位置集是唯一的。也就是说，我们钦定后，构造出来的一定是互不相同的。

接下来 \(f(0,x-1)\) 这一部分直接 \(dp\) 即可。注意到，这种东西实际上是可以抽象成 DAG 数路径数的，这东西直接矩阵加速即可。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int mod=(int)(1e9+7);
int n,K,X;

int fpow(int x,int y) {
	int res=1; x%=mod;
	while(y) {
		if(y&1) res=res*x%mod;
		y>>=1; x=x*x%mod;
	} return res;
}

struct Mat {
	int a[41][41];
	Mat() {
		memset(a,0,sizeof(a));
	}
	void clr() {
		memset(a,0,sizeof(a));
	}
}E,F;

Mat mul(Mat &f,Mat &g) {
	Mat res;
	for(int i=0;i<X;i++)
		for(int j=0;j<X;j++)
			for(int k=0;k<X;k++)
				res.a[i][j]=(res.a[i][j]+f.a[i][k]*g.a[k][j]%mod)%mod;
	return res;
}

void sol() {
	cin>>n>>X>>K;
	int ans=fpow(2*K+1,n-1)*(X+K)%mod;
	E.clr(); F.clr();
	for(int i=0;i<X;i++) F.a[0][i]=1;
	for(int i=0;i<X;i++) {
		for(int j=0;j<X;j++) {
			if(abs(i-j)<=K) E.a[i][j]=1;
		}
	}
	int qwq=n-1;
	while(qwq>0) {
		if(qwq&1) F=mul(F,E);
		qwq>>=1; E=mul(E,E);
	}
	for(int i=0;i<X;i++) ans=(ans-F.a[0][i]+mod)%mod;
	cout<<(ans%mod+mod)%mod<<'\n';
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int T; cin>>T; while(T--) sol();
	return 0;
} 

D.XOR Construction

注意到如果确定了第一个，其他一定是确定的。

即 \(b_i=pre_{i-1}^b_1\)，\(pre\) 为 \(a\) 的前缀异或。

那么限制有两个，一个是均不相同。

不妨考虑相同，即 \(pre_{i-1}^b_1=pre{j-1}^b_1\)，即二者 \(pre\) 相同，这与我们选取 \(b_1\) 是无关的。

另一个限制就是最大的数 \(\le n-1\)，这个限制我们直接变成 check 每个开头是否合法，变成最大异或扔到 01trie 上即可。

#include <bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
const int N=(int)(4e5+5);
int n,a[N],b[N],pre[N],ch[2][N*22],tot=1;

void ins(int x) {
	int p=1;
	for(int i=20;i>=0;i--) {
		bool c=((x>>i)&1);
		if(!ch[c][p]) ch[c][p]=++tot;
		p=ch[c][p];
	} 
}

int qry(int x) {
	int res=0,p=1;
	for(int i=20;i>=0;i--) {
		bool c=((x>>i)&1);
		if(ch[c^1][p]) {
			res|=(1<<i);
			p=ch[c^1][p];
		} else p=ch[c][p];
	}
	return res;
}

void sol() {
	for(int i=2;i<=n;i++) b[i]=(pre[i-1]^b[1]);
	for(int i=1;i<=n;i++) cout<<b[i]<<' ';
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<n;i++) cin>>a[i];
	for(int i=1;i<n;i++) pre[i]=(pre[i-1]^a[i]);
	for(int i=1;i<n;i++) ins(pre[i]);
	for(int i=0;i<n;i++) {
		int qwq=qry(i);
		if(qwq<=n-1) {
			b[1]=i; sol(); return 0;
		}
	}
	return 0;
}