시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
You are a student looking for a job. Today you had an employment examination for an IT company. They asked you to write an efficient program to perform several operations. First, they showed you an $N \times N$ square matrix and a list of operations. All operations but one modify the matrix, and the last operation outputs the character in a specified cell. Please remember that you need to output the final matrix after you finish all the operations.
Followings are the detail of the operations:
First line of each testcase contains nine integers. First two integers in the line, N and Q, indicate the size of matrix and the number of queries, respectively $(1 \leq N,Q \leq 40,000)$. Next three integers, A B, and C, are coefficients to calculate values in initial matrix $(1 \leq A,B,C \leq 1,000,000)$, and they are used as follows: $A_{r,c} = (r * A + c * B) mod C$ where r and c are row and column indices, respectively $(1\leq r,c\leq N)$. Last four integers, D, E, F, and G, are coefficients to compute the final hash value mentioned in the next section $(1 \leq D \leq E \leq N, 1 \leq F \leq G \leq N, E - D \leq 1,000, G - F \leq 1,000)$. Each of next Q lines contains one operation in the format as described above.
Output a hash value h computed from the final matrix B by using following pseudo source code.
h <- 314159265 for r = D...E for c = F...G h <- (31 * h + B_{r,c}) mod 1,000,000,007
where "<-" is a destructive assignment operator, "for i = S...T" indicates a loop for i from S to T (both inclusive), and "mod" is a remainder operation.
2 1 3 6 12 1 2 1 2 WR 1 1 1
676573821
2 1 3 6 12 1 2 1 2 RL
676636559
2 1 3 6 12 1 2 1 2 RH
676547189
39989 6 999983 999979 999961 1 1000 1 1000 SR 1 39989 SC 1 39989 RL RH RR RV
458797120