题解：P12595 出生于驾校

shinzAnmono · 2025-05-24 18:16:04 · 题解

设 P=\lfloor\log_2 n\rfloor，则 \sum_{i=0}^P2^i=O(n)。而所有修改操作都是全局操作，说明 a_i 的系数和后来加上的值均相同。

设 f_{i,j} 表示满足 x \bmod 2^i=j 的位置的 a_x 和。显然 f_{i,j}=f_{i+1,j}+f_{i+1,j+2^i}，即可 O(n) 预处理。

维护两个懒标记 add 和 mul，每次全局加操作直接改变 add，全局乘要对 add 和 mul 都 \times x。答案即为 f_{i,j}\times mul+add\times C(i,j)，C(i,j) 表示 x\bmod 2^i=j 的位置的个数。

#include<iostream>
#include<algorithm>
const int sz=4e7+10;
const int mod=998244353;
unsigned X,Y,Z;
unsigned rnd(){
  X^=Y<<(Z&31),Y^=Z>>(X&31),Z^=X<<(Y&31);
  X^=X>>5,Y^=Y<<17,Z^=Z>>6;
  return X;
}
int a[sz],b[sz<<1],*ptr=b,*sum[30];
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n,q,vl,vr;
  std::cin>>n>>q>>vl>>vr>>X>>Y>>Z;
  for(int i=0;i<n;i++)a[i]=rnd()%mod;
  int p=std::__lg(n);
  sum[p]=ptr;
  for(int i=0;i<1<<p;i++){
    for(int j=i;j<n;j+=1<<p)sum[p][i]+=a[j];
    sum[p][i]%=mod,ptr++;
  }
  for(int k=p-1;k>=0;k--){
    sum[k]=ptr;
    for(int i=0;i<1<<k;i++)sum[k][i]=(sum[k+1][i]+sum[k+1][i+(1<<k)])%mod,ptr++;
  }
  auto cnt=[&](int k,int p){return n/(1<<k)+(p<n%(1<<k));};
  long long ans=0,addtag=0,multag=1;
  while(q--){
    int op=rnd()%3,x,y;
    if(op==0)x=rnd()%mod,addtag=(addtag+x)%mod;
    if(op==1)x=rnd()%mod,multag=multag*x%mod,addtag=addtag*x%mod;
    if(op==2)x=rnd()%(vr-vl+1)+vl,y=rnd()%(1<<x),ans^=(sum[x][y]*multag+cnt(x,y)*addtag)%mod;
  }
  std::cout<<ans<<"\n";
  return 0;
}