csp模拟50
异或
疑惑是不是只有我是数位dp
考虑一个数 \(x\) 做出的贡献是这个数抑或上 \(x+1\) 也就是这个数二进制拆分下末尾连续1的长度加 1，所以直接数位dp，
\(len\) 表示长度，若这位为1则 \(len+1\) 否则变为 \(0\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100;
int num[N];
int dp[N][N][2];
int solve(int pos,int len,int limit,int fk){
if(!pos) return len+1;
if(!limit && dp[pos][len][fk]!=-1) return dp[pos][len][fk];
int up;
if(limit) up=num[pos];
else up=1;
int ans=0;
for(int i=0;i<=up;i++){
int en;
if(i==1) en=len+1;
else en=0;
if(fk==1){
ans+=solve(pos-1,en,limit&(i==up),1);
continue;
}
ans+=solve(pos-1,en,limit&(i==up),0);
}
if(!limit) dp[pos][len][fk]=ans;
return ans;
}
signed main(){
int n;
scanf("%lld",&n);
memset(dp,-1,sizeof(dp));
n--;
int cnt=0;
while(n){
num[++cnt]=n&1;
n>>=1;
}
int ans=solve(cnt,0,1,1);
cout<<ans<<endl;
}
树
首先需要明确的是，\(a\) 子树中所有与 \(a\) 的距离模 \(x\) 等于 \(y\) 的节点就是 \(a\) 子树中深度模 \(x\) 等于 \((dep_a+y)\mod x\)（下文设其为 \(k\)）的节点。这样我们就可以把修改转化为将一个点的子树内所有深度模 \(x\) 为 \(k\) 的节点权值加上 \(z\)。
考虑暴跳，此时 \(x>\sqrt n\) ，然后进行分块，对于散块暴力，整块打标记，设 \(DS1_{dep,i}\) 表示深度为 \(dep\) 的编号为 \(i\) 的块的变化值，然后差分求，复杂度 修 \(O(1)\) 跳 \(O(\sqrt n)\) 查 \(O(\sqrt n)\)。
再考虑 \(x<\sqrt n\) ,此时暴跳会使复杂变成 \(O(n)\) ,所以根号分治，设 \(DS2_{x,k,i}\) 表示深度 \(\mod x\) 为 \(k\) 的在第 \(i\) 块的变化，复杂度 \(\sqrt n\), 查 \(\sqrt n\)。
查询的时候，对于散块直接暴力，整块分两种情况直接加就可以。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=3*1e5+10;
int head[N*2],ver[N*2],nex[N*2],tot=0;
int B1,B2;
int dep[N],id[N],cnt=0,size[N],d[N];
int pos[N],l[N],r[N],t;
int s[N],DS1[203][203][203],DS2[N][203];
int n,q;
void add(int x,int y){
ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}
void dfs(int x,int fa){
dep[x]=dep[fa]+1;
id[x]=++cnt;
d[cnt]=dep[x];
size[x]=1;
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(y==fa) continue;
dfs(y,x);
size[x]+=size[y];
}
}
void change(int L,int R,int x,int k,int z,int y,int kk){
int p=pos[L],q=pos[R];
if(p==q){
for(int i=L;i<=R;i++) if(d[i]%x==k) s[i]+=z;
}
else{
for(int i=L;i<=r[p];i++) if(d[i]%x==k) s[i]+=z;
for(int i=l[q];i<=R;i++) if(d[i]%x==k) s[i]+=z;
if(x<=B2){
for(int i=p+1;i<=q-1;i++){
DS1[x][k][i]+=z;
}
}
else{
for(int i=kk;i<=n;i+=x){
DS2[i][p+1]+=z;DS2[i][q]-=z;
}
}
}
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0);
B1=1500,B2=200;
t=n/B1;
for(int i=1;i<=n/B1;i++){
l[i]=(i-1)*B1+1;
r[i]=i*B1;
}
if(r[t]<n) t++,l[t]=r[t-1]+1,r[t]=n;
for(int i=1;i<=t;i++){
for(int j=l[i];j<=r[i];j++){
pos[j]=i;
}
}
for(int w=1;w<=q;w++){
int op,x,y,v,z;
scanf("%d",&op);
if(op==1){
scanf("%d%d%d%d",&v,&x,&y,&z);
change(id[v],id[v]+size[v]-1,x,(dep[v]+y)%x,z,y,(dep[v]+y));
}
else{
scanf("%d",&v);
int ans=s[id[v]];
for(int i=1;i<=B2;i++){
ans+=DS1[i][dep[v]%i][pos[id[v]]];
}
for(int i=1;i<=pos[id[v]];i++){
ans+=DS2[dep[v]][i];
}
printf("%d\n",ans);
}
}
}