[SCOI2014]方伯伯打扑克

· · 题解

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

大致题意：

有一个 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 异或的前缀和是有规律的！！！规律如下：

于是考虑怎么把这个柿子变成一段连续的值域，这个 \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 的东西：

你会发现当 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 的那一位上的数就行。

这个有点复杂。

先随便打个表：

输入 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)。

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

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