题解：P10200 [湖北省选模拟 2024] 花神诞日 / sabzeruz

今年二月份的时候不会做，现在看来觉得自己当时好菜啊。

思路

首先是一个结论，

\forall a<b<c,a\oplus c>\min\{a\oplus b,b\oplus c\}

，其中

\oplus

是异或。换句话说，一个集合中异或和最小的两个数必然是从小到大排序后相邻的两个数。证明考虑丢到 trie 树上找到第一个不同位。

所以给

a

排个序，问题变成给每个元素染成红蓝两种颜色之一，要求相邻红色的异或和

\ge k_1

，相邻蓝色异或和

\ge k_2

，必须两种颜色都有，求方案数。

这个题意长得很像什么？是不是很像 CSP-S2024 T3？

考虑一样地设状态。设

dp(i,j,0/1)

表示当前已经决定了前

i

个元素的颜色，第

i

个元素的颜色是红/蓝，和

i

颜色不同的最后一个元素是

j

。

转移分两种，首先是

i+1

和

i

颜色相同，此时

j\le i-1

：

dp(i+1,j,0)=dp(i,j,0)[a_{i+1}\oplus a_i\ge k_1]

dp(i+1,j,1)=dp(i,j,1)[a_{i+1}\oplus a_i\ge k_2]

其中方括号是艾弗森括号。然后是

i+1

和

i

颜色不同，也就是和

j

颜色相同：

dp(i+1,i,0)=\sum\limits_{j=0}^{i-1}dp(i,j,1)[a_{i+1}\oplus a_j\ge k_1]

dp(i+1,i,1)=\sum\limits_{j=0}^{i-1}dp(i,j,0)[a_{i+1}\oplus a_j\ge k_2]

初值为

a_0=\infty,dp(1,0,0)=dp(1,0,1)=1

。答案为

\sum\limits_{i=1}^{n-1}(dp(n,i,0)+dp(n,i,1))

。注意此处

i

是从

1

开始，因为两种颜色都要有。

考虑优化。我们对

i

扫描线，维护数列

dp(i,*,0),dp(i,*,1)

的变化。

先考虑后两个转移。需要快速维护满足

a_{i+1}\oplus a_j\ge k_t

的

dp(i,j,t\oplus t)

的和。异或问题丢上 01-trie。我们在

a_j

对应的叶子处维护

dp(i,j,*)

，每个节点维护子树和。上面这个问题很容易在 trie 上做，如果

k_t

的这一位是

1

就递归到这一位异或

a_{i+1}

为

1

的子树，否则返回异或为

1

的子树和加上递归到异或后为

0

的子树的结果。

然后再是前两个。既然上 trie 树了那也好处理，如果

a_{i+1}\oplus a_i\ge k_t

就不修改

dp(i,*,t)

，否则打上 tag 赋值为

0

，访问的时候像线段树一样下传 tag 即可。

最后统计答案不能去

a_0

的子树，原因同上。

时间复杂度

O(n\log V)

。

代码

CPP

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
using namespace std;
const int MAXN=2e5+1,MOD=1e9+7;
int n;
ll a[MAXN],k[2];
int rt=1,cnt=1,nxt[MAXN*64][2],s[2][MAXN*64],tag[MAXN*64];
inline void psd(int now){
	if(tag[now]&1){
		if(nxt[now][0]) s[0][nxt[now][0]]=0,tag[nxt[now][0]]|=1;
		if(nxt[now][1]) s[0][nxt[now][1]]=0,tag[nxt[now][1]]|=1;
	}
	if(tag[now]&2){
		if(nxt[now][0]) s[1][nxt[now][0]]=0,tag[nxt[now][0]]|=2;
		if(nxt[now][1]) s[1][nxt[now][1]]=0,tag[nxt[now][1]]|=2;
	}
	tag[now]=0;
	return;
}
inline void upd(int now){
	(s[0][now]=s[0][nxt[now][0]]+s[0][nxt[now][1]])>=MOD&&(s[0][now]-=MOD);
	(s[1][now]=s[1][nxt[now][0]]+s[1][nxt[now][1]])>=MOD&&(s[1][now]-=MOD);
	return;
}
void mdf(int&now,int dep,ll v,int val,int id){
	if(!now) now=++cnt;
	if(dep==-1) return s[id][now]=val,void();
	psd(now);
	mdf(nxt[now][v>>dep&1],dep-1,v,val,id);
	upd(now);
	return;
}
int qry(int now,int dep,ll v,bool id){//s[id^1] of v^a[i]>=k[id]
	if(!now) return 0;
	if(dep==-1) return s[id^1][now];
	psd(now);
	if(k[id]>>dep&1) return qry(nxt[now][(v>>dep&1)^1],dep-1,v,id);
	else{
		int ans=s[id^1][nxt[now][(v>>dep&1)^1]]+qry(nxt[now][v>>dep&1],dep-1,v,id);
		ans>=MOD&&(ans-=MOD);
		return ans;
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k[0]>>k[1];
	F(i,1,n) cin>>a[i];
	sort(a+1,a+n+1);
	a[0]=1ll<<60;
	mdf(rt,60,a[0],1,0),mdf(rt,60,a[0],1,1);
	F(i,1,n-1){
		int dp0,dp1;
		dp0=qry(rt,60,a[i+1],0),dp1=qry(rt,60,a[i+1],1);
		if((a[i+1]^a[i])<k[0]) tag[rt]|=1,s[0][rt]=0;
		if((a[i+1]^a[i])<k[1]) tag[rt]|=2,s[1][rt]=0;
		mdf(rt,60,a[i],dp0,0),mdf(rt,60,a[i],dp1,1);
	}
	cout<<((s[0][rt]+s[1][rt]-s[0][nxt[rt][1]]-s[1][nxt[rt][1]])%MOD+MOD)%MOD;
	return 0;
}

题解：P10200 [湖北省选模拟 2024] 花神诞日 / sabzeruz

文章操作

思路

代码

相关推荐

评论

题解：P10200 [湖北省选模拟 2024] 花神诞日 / sabzeruz