[SCOI2014] 方伯伯打扑克
题目描述
有 m 堆牌,编号为 0,1,…,m−1。第 i 堆有 2ni 张牌,开始时从上到下依次标为 1,2,…,2ni。
一次洗牌将当前位置为奇数的牌按原相对顺序移到前面,位置为偶数的牌留在后面,且也保持相对顺序。例如 1,2,3,4,5,6,7,8 洗一次得到 1,3,5,7,2,4,6,8,再洗一次得到 1,5,2,6,3,7,4,8。
第 i 堆洗 xi 次后,设第 j 张牌上的数字是 aj。把第 li 张至第 ri 张牌上的数字各加 ti,再将这些结果按位异或。所得异或值对 2ni−1 取模,记为 ansi。
第 0 堆的参数由输入给出。对 i≥1,用上一堆的结果按以下顺序计算下一堆参数:
$$\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>ri,交换两者。之后用交换后的值计算
$$\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。
输入格式
第一行一个整数 m。第二行六个整数 n0,x0,l0,r0,t0,Base。
输出格式
输出一行一个整数,表示 ansm−1。
样例
2
5 1 4 27 3 15
2700
样例中 ans0=1。下一堆的参数为 n1=16、l1=7、r1=1795、x1=1791、t1=1802。
数据范围
| 原题比例 |
条件 |
| 10% |
m≤100 |
| 20% |
m≤5×105,ni≤20,Base≤16 |
| 60% |
m≤5×105,ni≤60,Base≤55 |
| 100% |
m≤5×106,ni≤60,Base≤55 |
初始输入的牌位要求为 1≤l0≤r0≤2n0,0<x0,t0<109。Base 是正整数。后续参数根据公式的取模范围确定。