7.14 冲刺国赛模拟 36
T1 染色题
关键性质是奇数偶数位上可以放置的只有两种，若 \(i\) 和 \(i-2\) 选的颜色不同，那么在 \(i\) 位置放一个球，\([l,r]\) 的限制等价于 \([l+2,r]\) 中奇数位和偶数位不同时有球。
设 \(f_i\) 为 \(i\) 放置一个球的合法方案数，这样直接枚举上一个球所在位置，注意到奇偶性相同的没有限制，不同的只能转移一个前缀，前缀和优化 DP。
点击查看代码
int n,m;
pii p[maxn];
int cnt=0;
int lpos[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int tag[maxn<<2];
inline void push_down(int rt){
if(tag[rt]){
tag[rt<<1]=tag[rt],tag[rt<<1|1]=tag[rt];
tag[rt]=0;
}
}
void update(int rt,int l,int r,int pl,int pr,int k){
if(pl<=l&&r<=pr) return tag[rt]=k,void();
push_down(rt);
if(pl<=mid) update(lson,pl,pr,k);
if(pr>mid) update(rson,pl,pr,k);
}
void dfs(int rt,int l,int r){
if(l==r) return lpos[l]=tag[rt]?tag[rt]:l,void();
push_down(rt);
dfs(lson),dfs(rson);
}
#undef mid
#undef lson
#undef rson
}S;
int f[maxn];
int sum[maxn][2];
int main(){
freopen("colour.in","r",stdin);
freopen("colour.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=m;++i){
int l=read()+2,r=read();
if(l<r) p[++cnt]=make_pair(l,r);
}
sort(p+1,p+1+cnt,[&](pii A,pii B){
return A.fir>B.fir;
});
for(int i=1;i<=cnt;++i){
S.update(1,1,n,p[i].fir,p[i].sec,p[i].fir);
}
S.dfs(1,1,n);
f[1]=4,sum[1][1]=4;
for(int i=2;i<=n;++i){
f[i]=(sum[i-2][i&1]+sum[lpos[i]-1][i&1^1])%mod;
sum[i][i&1^1]=sum[i-1][i&1^1],sum[i][i&1]=(sum[i-1][i&1]+f[i])%mod;
}
printf("%d\n",(sum[n][0]+sum[n][1])%mod);
return 0;
}
T2 石头剪刀布
朴素规则可以倍增处理某个类型胜出的概率，在此基础上研究。
\(l=r\) 的特殊性质也可以倍增处理，具体是合并时讨论 \(u\) 出现在哪一侧。
\(L=l,R=r\) 的特殊性质注意到这个合并是满足分配律的，也就是可以批量处理某个区间全部作为 \(u\) 和某个区间全部不作为 \(u\) 合并。
正解就呼之欲出了，类似线段树去求解，如果 \([l,r]\) 与一个子区间有交，那么递归求 \(u\) 在这个子区间的情况并与 \(u\) 不在另一子区间的情况合并。
点击查看代码
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int n,m;
char s[maxn];
struct Data{
ll R,P,S;
Data()=default;
Data(ll R_,ll P_,ll S_):R(R_),P(P_),S(S_){}
Data operator+(const Data &rhs)const{
Data res;
res.R=(R+rhs.R)%mod,res.P=(P+rhs.P)%mod,res.S=(S+rhs.S)%mod;
return res;
}
};
inline Data merge(Data A,Data B){
Data res;
res.R=(A.R*B.R%mod+(A.R*B.P%mod+A.P*B.R%mod)%mod*inv3%mod+(A.R*B.S%mod+A.S*B.R%mod)%mod*inv3*2%mod)%mod;
res.P=(A.P*B.P%mod+(A.R*B.P%mod+A.P*B.R%mod)%mod*inv3*2%mod+(A.P*B.S%mod+A.S*B.P%mod)%mod*inv3%mod)%mod;
res.S=(A.S*B.S%mod+(A.R*B.S%mod+A.S*B.R%mod)%mod*inv3%mod+(A.P*B.S%mod+A.S*B.P%mod)%mod*inv3*2%mod)%mod;
return res;
}
Data f[maxn][19],g[maxn][19];
Data solve(int l,int r,int pl,int pr,int k){
if(pl<=l&&r<=pr) return g[l][k];
Data res=Data(0,0,0);
if(pl<=l+(1<<k-1)-2) res=res+merge(solve(l,l+(1<<k-1)-2,pl,pr,k-1),f[r-(1<<k-1)+1][k-1]);
if(pr>=r-(1<<k-1)+2) res=res+merge(f[l][k-1],solve(r-(1<<k-1)+2,r,pl,pr,k-1));
return res;
}
int main(){
freopen("rps.in","r",stdin);
freopen("rps.out","w",stdout);
n=read(),m=read();
scanf("%s",s+1);
for(int i=1;i<=n;++i){
if(s[i]=='R') f[i][0]=g[i][1]=Data(1,0,0);
else if(s[i]=='P') f[i][0]=g[i][1]=Data(0,1,0);
else f[i][0]=g[i][1]=Data(0,0,1);
}
for(int k=1;k<=18;++k){
for(int i=1;i+(1<<k)-1<=n;++i){
f[i][k]=merge(f[i][k-1],f[i+(1<<k-1)][k-1]);
}
}
for(int k=2;k<=18;++k){
for(int i=1;i+(1<<k)-2<=n;++i){
g[i][k]=merge(g[i][k-1],f[i+(1<<k-1)-1][k-1])+merge(f[i][k-1],g[i+(1<<k-1)][k-1]);
}
}
while(m--){
int L=read(),R=read(),l=read(),r=read();
Data ans=solve(L,R,l,r,__lg(R-L+2));
printf("%lld\n",ans.R*q_pow((l-L)&1?(r-l+1)/2:(r-l+2)/2,mod-2,mod)%mod);
}
return 0;
}
T3 树状数组
两个关键性质：
-
低 \(p\) 位均为 \(0\) 的所有数在进行同样后缀的操作后低 \(p\) 位相同。
-
运算过程中，两个低 \(p\) 位均为 \(0\) 的时刻之间的 \(-1\) 操作不会影响到比 \(p\) 位更高的，也就是可以直接异或和。
考虑预处理 \(f_{p,i}\) 表示在 \(i\) 操作之后低 \(p\) 为均为 \(0\) 的数下一次低 \(p\) 为均为 \(0\) 的位置，\(g_{p,i,0/1}\) 表示在 \(i\) 操作之后低 \(p-1\) 位均为 \(0\) 且第 \(p\) 位为 \(0/1\) 的数下一次低 \(p\) 位均为 \(0\) 的位置。
预处理过程是倒序枚举，如果已经处理了 \(p-1\)，那么 \(p\) 的只需讨论当前操作并在 \(g_{p,f_{p-1,i},0/1}\) 转移过来。
之后预处理 \(ans_i\) 表示 \(i\) 位置输入 \(0\) 后进行操作最终的结果。这个过程找到最大的 \(p\) 使得 \(f_{p,i}\) 存在，那么 \(ans_{f_{p,i}+1}\) 与 \(ans_i\) 相比，低 \(p\) 位都相同，剩下的不会被 \(-1\) 影响，直接异或和。
最后求答案考虑一次消去 \(\mathrm{lowbit}\)，每次跳到 \(g_{p,i,1}\) 的位置，这个过程依旧是低位不变，高位异或和。最终到达的位置也是和 \(ans_i\) 处理即可。
点击查看代码
#define lowbit(x) (x&-x)
int n,m,k,A,B;
int a[maxn];
int xorsum[maxn];
int f[31][maxn],g[31][maxn][2];
int ans[maxn];
int lastans;
int main(){
freopen("fenwick.in","r",stdin);
freopen("fenwick.out","w",stdout);
n=read(),m=read(),k=read(),A=read(),B=read();
for(int i=1;i<=n;++i){
a[i]=read();
xorsum[i]=xorsum[i-1]^(a[i]==-1?0:a[i]);
}
f[0][n]=n+1,g[0][n][0]=n,g[0][n][1]=n+1,g[0][n+1][0]=n+1,g[0][n+1][1]=n+1;
for(int i=n-1,last=(a[n]==-1||a[n]&1)?n:n+1;i>=0;--i){
if(a[i+1]==-1||!(a[i+1]&1)) f[0][i]=i+1;
else f[0][i]=g[0][i+1][1];
g[0][i][0]=i,g[0][i][1]=last;
if(a[i]==-1||a[i]&1) last=i;
}
for(int p=1;p<k;++p){
f[p][n]=n+1,g[p][n][0]=n,g[p][n][1]=n+1,g[p][n+1][0]=n+1,g[p][n+1][1]=n+1;
for(int i=n-1;i>=0;--i){
if(a[i+1]==-1||lowbit(a[i+1])>(1<<p)) f[p][i]=i+1;
else f[p][i]=g[p][f[p-1][i]][((xorsum[f[p-1][i]]^xorsum[i])>>p)&1];
g[p][i][0]=i;
if(a[i+1]==-1) g[p][i][1]=i+1;
else g[p][i][1]=g[p][f[p-1][i]][((xorsum[f[p-1][i]]^xorsum[i])>>p)&1^1];
}
}
for(int i=n;i>=1;--i){
int high=-1;
for(int p=k-1;p>=0;--p){
if(f[p][i-1]!=n+1){
high=p;
break;
}
}
if(high==-1) ans[i]=xorsum[n]^xorsum[i-1];
else ans[i]=ans[f[high][i-1]+1]^(((xorsum[f[high][i-1]]^xorsum[i-1])>>high+1)<<high+1);
}
while(m--){
int l=read(),x=read();
l^=(1ll*A*lastans+B)%n,x^=(1ll*A*lastans+B)%(1<<k);
--l;
while(x){
int low=__lg(lowbit(x));
if(g[low][l][1]==n+1) break;
x=((x>>low+1)<<low+1)^(((xorsum[g[low][l][1]]^xorsum[l])>>low+1)<<low+1);
l=g[low][l][1];
}
if(!x) lastans=ans[l+1];
else{
int low=__lg(lowbit(x));
lastans=(x>>low<<low)^ans[l+1];
}
printf("%d\n",lastans);
}
return 0;
}