#P3623. CATS

    ID: 1780 传统题 2000ms 256MiB 尝试: 16 已通过: 7 难度: 7 上传者: 标签>难度分类提高+/省选-构造与建模不变量分析奇偶性分析位运算Brian Kernighan 算法CF2300ByHta

CATS

[新加坡 NOI 2014] CATS

题目描述

熊猫先生想用 CATS(Counter and Two Stacks)语言写一个程序。给出 X,L,NX,L,N 时,他原本想求严格大于 LL 的第 XX 个 NN 的倍数。他用到了负数,并且有些指令被执行了两次。你需要求出下面这段程序实际打印的值。

CATS 可以操作一个计数器 COUNTER\mathrm{COUNTER} 和两个栈 S1,S2\mathrm{S1},\mathrm{S2}。两栈初始化时各含无穷多个 00。普通的 PUSH\mathrm{PUSH} 和 POP\mathrm{POP} 分别压入一个数和弹出栈顶。 ADD\mathrm{ADD} 弹出栈顶的两个数,并压入它们的和。尝试压入负数时,该数不会入栈,整座栈中的每个数(包括无限延伸的部分)都会翻转其二进制最低位。翻转最低位等价于与 11 异或,例如 44 和 55 在翻转后互换。

以下伪代码用 T1 和 T2 分别表示 S1 和 S2 当时的栈顶。每次询问都从两个初始栈开始。

COUNTER = X
WHILE COUNTER > 0
    S2 PUSH T1
    S1 POP
    FLIP LAST BINARY BIT OF ALL NUMBERS IN S1
    IF T2 > L
        COUNTER = COUNTER - 1
        IF COUNTER == 0 PRINT T2
    ELSE
        S2 PUSH N
        S2 PUSH N
        S2 ADD
        S2 ADD
        S1 PUSH T2
        S1 PUSH T2
        S2 POP
        S2 POP

输入格式

第一行一个正整数 QQ,表示询问数。随后 QQ 行各有三个正整数 X,L,NX,L,N,保证 LL 不是 NN 的倍数。

输出格式

输出 QQ 行,每行一个整数。第 ii 行是熊猫先生的程序对第 ii 个询问打印的唯一一个整数。

2
4 5 2
18 6 4
8
9

样例解释

表中为第一组询问每次进入循环前的状态,只列出 S1 最上面的四个元素,最左边是栈顶。

COUNTER S1
4 0 0 0 0
4 4 1 1
8 8 5 0
3 9 4 1 1
2 5 0 0 0
9 9 1 1
1 8 0 0 0

最后一次执行循环时,COUNTER 降到 00,因此打印 88。

数据范围

当前 OJ 归档有一份包含 Q=223100Q=223100 个询问的测试输入,1≤X,L,N≤260−11\le X,L,N\le 2^{60}-1。

原赛六档数据如下。表内数值为上界,第一档的 QQ 固定为 11。

档次 分值 QQ XX LL NN
1 4 11 10610^6 2020
2 5050 5050
3 500500 8080
4 10001000 10610^6
5 1000010000 230−12^{30}-1
6 5 100000100000 260−12^{60}-1