• [B] Easy Operation

  • 时间限制: 8000 ms　内存限制: 262144 K
  • 问题描述

  • There is a set named "setA" which only has a number M. And we assign 0 to W initially.

    Also, there are N operations which consists of 8 parameters and a ID number. The ith (1 - Based) operation's ID number is i.

    Other 8 parameters are:

    Fa Fc X L R A B C

    For each operation (example for ith operation), we should follow these steps.

    0. Before the operation, we let F = (Fa * W + Fc) Mod i .

    1. Find the number of “Good numbers”, we assume the result is Count.

    Good number must satisfied three condition:

    (1) The number P from the“setA”.

    (2) The P's ID is equal or greater than F.

    (3) L <= (P xor X) <= R (xor meas exclusive OR operation).

    2. Output the Count and assign Count to W.

    3. Insert (W * A + B) Mod C to "setA", the ID of (W * A + B) Mod C is equal to the operation's ID, which means the ID of ( W * A + B ) Mod C is i too.

    Note_1: "setA" is not a unique set. (It contains same numbers probably)

    Note_2: The ID of M is 0.

  • 输入
  • There are a number T on first line shows there are T cases.
    For each case, there are 2 numbers N, M on the first line. The“setA”only contains number“M”initially (1 <= N <= 1e5 , 1 <= M <= 1e6).
    For the ith line (1 - Based) line under the first line, there is an operation, whose ID is i, on each line which consists of 8 integer parameters : Fa Fc X L R A B C.
    (0 <= L, X, R, Fc <= 1e6, 1 <= A, B, C, Fa <= 1e6)
    All test cases are generated randomly.
  • 输出
  • For each operation, output a number.
  • 样例输入
  • 3
2 0
1 0 2 0 3 1 2 4
1 2 2 1 5 1 2 4
3 8
8 6 3 2 6 6 6 1
1 7 8 2 6 2 5 4
8 1 0 5 8 7 5 1
4 1
1 3 1 7 9 5 6 2
8 9 2 6 7 3 5 1
5 9 2 3 6 7 9 9
1 4 6 5 7 1 7 7
  • 样例输出
  • 1
1
0
0
0
0
0
1
2
  • 提示
  • For the first test case.
2 0                                                                                                                                        
The set is {0} initially.
1 0 2 0 3 1 2 4   
F = (0 * 1 + 0) Mod 1 = 0. In this way, there is a good number 0, because 0’s ID is 0, and 0 xor 2 =0.
So we output 1 and insert (1 * 1 + 2) mod 4 = 3 to the set.  
The set is {0, 3} now.
1 2 1 5 1 2 4      
F = (1 * 1 + 2) Mod 2 = 1. In this way, there is a good number 3, becasue 3’s ID is 1, and 3 xor 2 = 1. 
So we output 1 and insert (1 * 1 + 2) mod 4 = 3 to the set.  
The set is {0 , 3 , 3} now.
  • 来源
  • Dshawn @BUAA
  • 操作

显示春菜