自动搬运

查看原文

来自洛谷，原作者为

	ForgotMe 花与剑无痕，高挂一轮明灯。银蝶染旧梦，生死莫再问。

搬运于2025-08-24 21:47:18，当前版本为作者最后更新于2021-04-08 15:05:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

记录一下这道神仙题。全网都没有题解，顺便来发一篇。

大致题意：

有一个 $1\sim 2^n$ 的序列，最开始第 $i$ 个位置上的数字为 $i$，有一个操作次数 $x$，每轮操作将奇数位置上的数提取出来依次放在前面，偶数上的位置的数放在依次后面，操作 $x$ 次后，将 $l\sim r$ 位置的数都加上 $t$，求 $l\sim r$ 位置上的数的异或和。$m$ 次询问 ，强制在线。

10 分做法。

暴力模拟即可，没啥好讲的。

20 分做法。

考虑一下这个操作是在干嘛，咦，每个数减去 $1$ 后不是 dX 那道 维护序列（P7442） 吗？

考虑直接写出操作后第 $i$ 个数的值：$(i\bmod dr )\times 2^r+\lfloor\dfrac{i}{dr}\rfloor+1$，其中 $r=x\bmod n$，$dr=2^{n-r}$，加 $1$ 是因为减去了 $1$，如果不懂这个柿子可以去看 dX 那个题。

贴一下暴力代码：

#include<cmath> 
#include<queue>
#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
const int MAXN=5e6+5;
LL m,n[MAXN],x[MAXN],L[MAXN],R[MAXN],TT[MAXN],Base,ans[MAXN],p,T;
void solve(int w){
	int r=x[w]%n[w];
	LL Ans=0,dr=1ll<<(n[w]-r),t=TT[w];
	for(LL i=L[w]-1;i<=R[w]-1;i++)Ans^=(((i%dr)<<r)+(i/dr)+t+1); 
	ans[w]=Ans&((p>>1)-1);
}
signed main(){
	scanf("%lld %lld %lld %lld %lld %lld %lld",&m,&n[0],&x[0],&L[0],&R[0],&TT[0],&Base);
	p=1ll<<n[0];
	solve(0);
	for(int i=1;i<m;i++){
		n[i]=(ans[i-1]+i-1)%5+Base;
		p=1ll<<n[i];
		L[i]=(ans[i-1]*2+L[i-1]+i-1)&(p-1);
		L[i]++;
		T=1ll<<(n[i]>>1);
		R[i]=(ans[i-1]+1+(L[i]&(T-1))*T)&(p-1);
		R[i]++;
		if(L[i]>R[i])swap(L[i],R[i]);
		x[i]=(R[i]-L[i]+TT[i-1]+i-1)&(p-1);
		TT[i]=(L[i]+R[i])&(p-1);
		solve(i);
	}
	printf("%lld\n",ans[m-1]);
	return 0;
} 

但是这个还是没啥用啊，照样 $10$ 分，来，我们来推柿子。

首先，把问题写成柿子：

$$\bigoplus_{i=l}^r[ (i\bmod dr)*2^{r}+\lfloor\dfrac{i}{dr}\rfloor+t+1 ] $$

相当于就是要求：

$$\bigoplus_{i=0}^N[ (i\bmod dr)*2^{r}+\lfloor\dfrac{i}{dr}\rfloor+t+1 ] $$

可能看到这个东西没啥想法，但没关系，我们来想一想跟异或有关的东西，$a\bigoplus a=0$ 有用吗？没用。但是，$0\sim N$ 异或的前缀和是有规律的！！！规律如下：

• $N\bmod 4=0$，答案为 $N$。
• $N\bmod 4=1$，答案为 $1$。
• $N\bmod 4=2$，答案为 $N+1$。
• $N\bmod 4=3$，答案为 $0$。

于是考虑怎么把这个柿子变成一段连续的值域，这个 $\bmod$ 刚好提供了这么一个条件，枚举取模后的值。

$$\bigoplus_{i=0}^{\min(dr-1,N)}\bigoplus_{j=0}^{\lfloor\frac{N-i}{dr}\rfloor}[i\times 2^{r}+j+t+1] $$

后面这个不就是一段连续的值域？设 $f(x)$ 表示 $\bigoplus_{i=0}^x i$，代进去。

$$[\bigoplus_{i=0}^{\min(dr-1,N)}f(i \times 2^r+\lfloor\frac{N-i}{dr}\rfloor+t+1)]\bigoplus[\bigoplus_{i=0}^{\min(N,dr-1)} f(i\times 2^{r}+t)] $$

暴力算就可以得到 $20$ 分的好成绩。

100 分做法。

还是回顾上面那个柿子：

$$[\bigoplus_{i=0}^{\min(dr-1,N)}f(i \times 2^r+\lfloor\frac{N-i}{dr}\rfloor+t+1)]\bigoplus[\bigoplus_{i=0}^{\min(N,dr-1)} f(i\times 2^{r}+t)] $$

左边较为复杂，先看右边，右边实际上是要解决这样子的一个子问题：

$$F(n,r,t)=\bigoplus_{i=0}^Nf(i\times 2^r+t)$$

这个怎么做啊，$n$ 这么大，$r$ 也很大，$t$ 也很大，反正都很大，还做个屁，数位 dp？显然不行，$m$ 有 $5\times 10^6$，显然只能 $\mathcal{O}(1)$。那怎么办呢？那就祭出我们的杀器-找规律。

先给出找规律的程序：

#include<cmath> 
#include<queue>
#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define int long long
LL f(LL n){
	if(n%4==1)return 1;
	else if(n%4==2)return n+1;
	else if(n%4==3)return 0;
	else return n;
}
signed main(){
	int n,R,t,ans=0;
	cin>>n>>R>>t;
	for(LL i=0;i<=n;i++){
		ans^=f(i*(1ll<<R)+t);
		cout<<i<<" "<<ans<<endl;
	}
	return 0;
} 

然后你会发现一些很 nb 的东西：

• $t$ 为奇数的时候：

你会发现当 $r$ 固定的时候，$t=1,3,5,7,9....$ 的时候，取值都为 $0$ 或 $1$，而且每 $4$ 个数字一循环。

举个栗子：

输入 $7\ 1\ 1$：

输出如下

0 1
1 1
2 0
3 0
4 1
5 1
6 0
7 0

你会发现 $1100,1100$ 这个东西反复出现。

输入 $7\ 1\ 3$：

输出如下

0 0
1 1
2 1
3 0
4 0
5 1
6 1
7 0

这次变成了 $0110,0110$。

继续打： 输入 $7\ 1\ 5$：

输出如下

0 1
1 1
2 0
3 0
4 1
5 1
6 0
7 0

你会发现这个循环节又回去了，于是猜测：对于当 $t$ 为奇数的时候，对于一个固定的 $r$，不同的循环节有两种，且对于 $t\bmod 4=1$ 的 $t$ 为同一种循环节，对于 $t\bmod 4=3$ 的 $t$ 又为同一种循环节。

证明啊，不会，找规律的精髓在于找到规律，而不是证明。

于是 $t$ 为奇数就可以做了，直接暴力找到 $t$ 所对应的循环节，然后返回 $n\bmod 4$ 的那一位上的数就行。

• $t$ 为偶数的时候：

这个有点复杂。

先随便打个表：

输入 $7\ 1\ 2$：

输出如下

0 3
1 7
2 0
3 8
4 3
5 15
6 0
7 16

哎，有长度为 $4$ 的循环节，而且 $x\bmod 4=0\ or\ x\bmod 4=2$ 的 $x$ 位置上的数都没变啊。换个栗子：

输入 $7\ 15\ 300000$：

输出如下

0 300000
1 98304
2 267232
3 131072
4 300000
5 229376
6 267232
7 786432

符合上面的结论，那哪些位置是没变的呢？

输入 $7\ 10\ 20$：

输出如下

0 20
1 1024
2 3092
3 0
4 4116
5 1024
6 7188
7 0

可以发现这次不变的位置是 $x\bmod 4=1\ or\ x\bmod 4=3$ 的 $x$。

经过大量数据验证：不变的位置是 $x\bmod 4=1\ or\ x\bmod 4=3$ 的 $x$，或者是 $x\bmod 4=0\ or\ x\bmod 4=2$ 的 $x$。

于是这个也可以做了，找到不变的两个位置，如果询问的位置 $\bmod\ 4$ 就是不变的位置，直接返回，否则就将前面那个不变的位置上的数异或上 $f(n\times 2^{r}+t)$。

最后，这两个规律合并起来就可以 $\mathcal{O}(1)$ 算出 $F$，但是会在 $r=0$ 的时候出错，特判一下即可，这个也是有规律的，留给读者自找。

$$[\bigoplus_{i=0}^{\min(dr-1,N)}f(i \times 2^r+\lfloor\frac{N-i}{dr}\rfloor+t+1)]\bigoplus F(\min(dr-1,N),r,t) $$

前面这个咋搞啊，发现 $\lfloor\dfrac{N-i}{dr}\rfloor$ 只有两种不同的取值，因为只循环到了 $\min(dr-1,N)$，讨论一下即可。

至此我们在 $\mathcal{O}(1)$ 的时间内解决了每一次询问，总时间复杂度 $\mathcal{O}(m)$。

至于这些神仙规律怎么证明，我也不会，如果有哪位大佬会证明希望可以分享一下。

代码的话就不放出来了，要的可以私信我。