Fox Socks

View as PDF

Submit solution

Points: 40
Time limit: 150.0s
Memory limit: 1G

Author:
Problem type
Facebook Hacker Cup 2015 Round 2

Mr. Fox sure loves his socks! He stores his many indistinguishable socks in a set of N bins, which are arranged in a circle and numbered in clockwise order. For every 1 \le i < N, the next bin clockwise of bin i is bin i+1, and the next bin clockwise of bin N is bin 1. Initially, the i^\text{th} bin contains S_i socks.

Never being quite satisfied with his sock collection, Mr. Fox would like to perform M operations on it, one after another. Each operation i may be of one of the following 4 types, determined by the value of O_i:

  • Given integers A_i, B_i, C_i, and D_i, add C_i + 0 * D_i socks to bin A_i, add C_i + 1 * D_i socks to the next bin clockwise of bin A_i, add C_i + 2 * D_i to the next bin clockwise of that one, and so on until this has been done for B_i bins. Determine the total number of socks added in this process.
  • Given integers A_i, B_i, and C_i, remove all of the socks from bin A_i and then add C_i socks to it. Do the same for the next bin clockwise of A_i, and so on until this has been done for B_i bins. Determine the sum of two values: the total number of socks removed in this process, and the total number of socks added in this process.
  • Given integers A_i and B_i, count the number of socks in bin A_i (without removing them), the number of socks in the next bin clockwise of A_i, and so on until the socks in B_i bins have been counted. Determine the total number of socks counted in this process.
  • Given integers A_i and B_i, check if bin A_i contains an odd number of socks. Do the same for the next bin clockwise of A_i, and so on until this has been done for B_i bins. Determine the total number of these bins that contain an odd number of socks.

Can you help Mr. Fox keep track of his socks?
Note the value calculated during each of the M operations as they're performed, and then output the sum of all M of the values modulo 10^9.

Input

Input begins with an integer T, the number of sock collections Mr. Fox has. For each sock collection, there are 7 lines containing the following space-separated integers:

  1. N M
  2. S_1 S_2 X_S Y_S Z_S
  3. O_1 O_2 X_O Y_O Z_O
  4. A_1 A_2 X_A Y_A Z_A
  5. B_1 B_2 X_B Y_B Z_B
  6. C_1 C_2 X_C Y_C Z_C
  7. D_1 D_2 X_D Y_D Z_D

The first two elements of each sequence of integers (S, O, A, B, C, and D) are given, and the rest are computed with the following pseudorandom generators:

  • S_i = (X_S * S_{i-2} + Y_S * S_{i-1} + Z_S) \bmod 10^9, for 3 \le i \le N
  • O_i = ((X_O * O_{i-2} + Y_O * O_{i-1} + Z_O) \bmod 4) + 1, for 3 \le i \le M
  • A_i = ((X_A * A_{i-2} + Y_A * A_{i-1} + Z_A) \bmod N) + 1, for 3 \le i \le M
  • B_i = ((X_B * B_{i-2} + Y_B * B_{i-1} + Z_B) \bmod N) + 1, for 3 \le i \le M
  • C_i = (X_C * C_{i-2} + Y_C * C_{i-1} + Z_C) \bmod 10^9, for 3 \le i \le M
  • D_i = (X_D * D_{i-2} + Y_D * D_{i-1} + Z_D) \bmod 10^9, for 3 \le i \le M

Output

For the ith sock collection, print a line containing Case #i: followed by the sum of all values calculated during each operation, modulo 10^9.

Constraints

1 \le T \le 20
2 \le N \le 1\,000\,000
2 \le M \le 1\,000\,000
0 \le S_i < 10^9
1 \le O_i \le 4
1 \le A_i \le N
1 \le B_i \le N
0 \le C_i < 10^9
0 \le D_i < 10^9

0 \le X_S, X_O, X_A, X_B, X_C, X_D < 10^9

0 \le Y_S, Y_O, Y_A, Y_B, Y_C, Y_D < 10^9

0 \le Z_S, Z_O, Z_A, Z_B, Z_C, Z_D < 10^9

Explanation of Sample

The first collection has 5 bins that all have 0 socks. None of the operations involve any socks at all, so the answer is 0.

The second collection has 5 bins with 1, 2, 3, 4, and 5 socks. Mr. Fox performs the operations 1, 2, 3, and 4 in order. For each operation, A = 1, B = 5, C = 0, D = 0. He first adds 0 socks to the bins, then removes all 15 socks, then counts the 0 remaining socks, and then counts 0 odd bins, for a total of 15.

The third collection also has 5 bins with 1, 2, 3, 4, and 5 socks. Mr. Fox performs the same operations, but this time C and D take on the values 1, 2, 3, and 4 in that order. He adds 15 socks to the bins, then removes all 30 socks and adds 2 socks to each bin, then counts those 10 socks, and then counts 0 odd bins. The total is then 15 + 30 + 10 + 10 = 65.

Sample Input

5
5 4
0 0 0 0 0
1 2 0 1 0
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0
5 4
1 2 0 1 1
1 2 0 1 0
1 1 0 0 0
5 5 0 1 4
0 0 0 0 0
0 0 0 0 0
5 4
1 2 0 1 1
1 2 0 1 0
1 1 0 0 0
5 5 0 1 4
1 2 0 1 1
1 2 0 1 1
5 2
1 2 0 1 1
4 4 0 0 0
1 1 0 0 0
5 5 0 0 0
0 0 0 0 0
0 0 0 0 0
100 100
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

Sample Output

Case #1: 0
Case #2: 15
Case #3: 65
Case #4: 6
Case #5: 505274484

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.


Comments

There are no comments at the moment.