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;
}
- Educational Codeforces Round Rated 157educational codeforces round rated educational codeforces round 157 round codeforces rated based educational codeforces round 151 construction educational codeforces round educational codeforces round 147 cf-educational educational codeforces round educational codeforces round 158 educational codeforces contest round educational codeforces monsters round