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

littlez_meow · 2024-11-16 18:14:19 · 题解

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

思路

首先是一个结论，\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：

其中方括号是艾弗森括号。然后是 i+1 和 i 颜色不同，也就是和 j 颜色相同：

初值为 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)。

代码

#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;
}