#P3596. [Scoi2014]方伯伯打扑克

    ID: 2803 传统题 1000ms 512MiB 尝试: 29 已通过: 5 难度: 8 上传者: 标签>难度分类提高+/省选-模拟与实现技巧坐标变换位运算异或前缀和异或抵消CF2500By佚名提供

[Scoi2014]方伯伯打扑克

[SCOI2014] 方伯伯打扑克

题目描述

有 mm 堆牌,编号为 0,1,…,m−10,1,\ldots,m-1。第 ii 堆有 2ni2^{n_i} 张牌,开始时从上到下依次标为 1,2,…,2ni1,2,\ldots,2^{n_i}。

一次洗牌将当前位置为奇数的牌按原相对顺序移到前面,位置为偶数的牌留在后面,且也保持相对顺序。例如 1,2,3,4,5,6,7,81,2,3,4,5,6,7,8 洗一次得到 1,3,5,7,2,4,6,81,3,5,7,2,4,6,8,再洗一次得到 1,5,2,6,3,7,4,81,5,2,6,3,7,4,8。

第 ii 堆洗 xix_i 次后,设第 jj 张牌上的数字是 aja_j。把第 lil_i 张至第 rir_i 张牌上的数字各加 tit_i,再将这些结果按位异或。所得异或值对 2ni−12^{n_i-1} 取模,记为 ansi\mathrm{ans}_i。

第 00 堆的参数由输入给出。对 i≥1i\ge1,用上一堆的结果按以下顺序计算下一堆参数:

$$\begin{aligned} n_i &= (\mathrm{ans}_{i-1}+i-1)\bmod 5+\mathrm{Base},\\ l_i &= (2\mathrm{ans}_{i-1}+l_{i-1}+i-1)\bmod 2^{n_i}+1,\\ h_i &= 2^{\lfloor n_i/2\rfloor},\\ r_i &= \bigl(\mathrm{ans}_{i-1}+1+(l_i\bmod h_i)h_i\bigr)\bmod 2^{n_i}+1. \end{aligned}$$

若此时 li>ril_i>r_i,交换两者。之后用交换后的值计算

$$\begin{aligned} x_i &= (r_i-l_i+t_{i-1}+i-1)\bmod 2^{n_i},\\ t_i &= (l_i+r_i)\bmod 2^{n_i}. \end{aligned}$$

求最后一堆牌的结果 ansm−1\mathrm{ans}_{m-1}。

输入格式

第一行一个整数 mm。第二行六个整数 n0,x0,l0,r0,t0,Basen_0,x_0,l_0,r_0,t_0,\mathrm{Base}。

输出格式

输出一行一个整数,表示 ansm−1\mathrm{ans}_{m-1}。

样例

2
5 1 4 27 3 15
2700

样例中 ans0=1\mathrm{ans}_0=1。下一堆的参数为 n1=16n_1=16、l1=7l_1=7、r1=1795r_1=1795、x1=1791x_1=1791、t1=1802t_1=1802。

数据范围

原题比例 条件
10%10\% m≤100m\le100
20%20\% m≤5×105m\le5\times10^5,ni≤20n_i\le20,Base≤16\mathrm{Base}\le16
60%60\% m≤5×105m\le5\times10^5,ni≤60n_i\le60,Base≤55\mathrm{Base}\le55
100%100\% m≤5×106m\le5\times10^6,ni≤60n_i\le60,Base≤55\mathrm{Base}\le55

初始输入的牌位要求为 1≤l0≤r0≤2n01\le l_0\le r_0\le 2^{n_0},0<x0,t0<1090<x_0,t_0<10^9。Base\mathrm{Base} 是正整数。后续参数根据公式的取模范围确定。