/ 
Time Limit: 3 sec / Memory Limit: 2048 MiB
配点 : 525 点
問題文
N 行 N 列のグリッドで表される市街地があります。上から i 行目・左から j 列目のマスをマス (i,j) と表します。各マスには 1 つずつカフェがあります。
あなたはミーティングを企画しています。参加者のうち、マス (i, j) に住む人の人数は (A_i \times B_j) \bmod M です。 マス (s_r,\ s_c) に住む参加者 1 人がマス (t_r,\ t_c) にあるカフェに行くときにかかる交通費は \max(|s_r - t_r|,\ |s_c - t_c|) です。
参加者全員をマス (i, j) にあるカフェへと集めるときにかかる交通費の合計を f(i, j) とします。
各マス (i,j) に対する以下の値をすべてのマスについて求めたときの、それらの bitwise XOR として得られる値を出力してください。
- f(i,j) + (i-1)N + (j-1)
bitwise XOR 演算とは
非負整数 A, B の bitwise XOR (A \oplus B で表す) は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k の bitwise XOR は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 1 \leq N \leq 1500
- 2 \leq M \leq 2 \times 10^6
- 1 \leq A_i \leq M-1 (1 \leq i \leq N)
- 1 \leq B_j \leq M-1 (1 \leq j \leq N)
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 \dots A_N B_1 \dots B_N
出力
答えを出力せよ。
入力例 1
4 19 2 3 1 1 3 4 4 10
出力例 1
467
各マスに住む参加者の人数を並べると \displaystyle \begin{bmatrix} 6 & 8 & 8 & 1 \\ 9 & 12 & 12 & 11 \\ 3 & 4 & 4 & 10 \\ 3 & 4 & 4 & 10 \end{bmatrix} となります。
たとえば f(1,2) の値は、次の 16 個の値の合計値 176 として得られます。
- マス (1,1) の住人 6 人がそれぞれ交通費 \max(|1 - 1|,\ |1 - 2|) = 1 をかけたときの総額 6 \times 1 = 6
- マス (1,2) の住人 8 人がそれぞれ交通費 \max(|1 - 1|,\ |2 - 2|) = 0 をかけたときの総額 8 \times 0 = 0
- マス (1,3) の住人 8 人がそれぞれ交通費 \max(|1 - 1|,\ |3 - 2|) = 1 をかけたときの総額 8 \times 1 = 8
- マス (1,4) の住人 1 人がそれぞれ交通費 \max(|1 - 1|,\ |4 - 2|) = 2 をかけたときの総額 1 \times 2 = 2
- \vdots
- マス (4,1) の住人 3 人がそれぞれ交通費 \max(|4 - 1|,\ |1 - 2|) = 3 をかけたときの総額 3 \times 3 = 9
- マス (4,2) の住人 4 人がそれぞれ交通費 \max(|4 - 1|,\ |2 - 2|) = 3 をかけたときの総額 4 \times 3 = 12
- マス (4,3) の住人 4 人がそれぞれ交通費 \max(|4 - 1|,\ |3 - 2|) = 3 をかけたときの総額 4 \times 3 = 12
- マス (4,4) の住人 10 人がそれぞれ交通費 \max(|4 - 1|,\ |4 - 2|) = 3 をかけたときの総額 10 \times 3 = 30
各マスにおける f(i,j) の値を並べると \displaystyle \begin{bmatrix} 220 & 176 & 179 & 224 \\ 199 & 140 & 136 & 182 \\ 212 & 159 & 143 & 178 \\ 255 & 215 & 201 & 218 \end{bmatrix} となります。
入力例 2
6 67 1 6 9 2 3 1 1 10 3 7 2 2
出力例 2
1021
入力例 3
20 676767 60932 508200 22883 481150 426836 554098 276223 307959 133025 573906 17711 413230 274246 500277 524959 477728 546547 43099 324227 660187 552697 293978 246000 159233 213736 628198 394200 194076 618720 453035 615100 331522 669419 180856 530693 399531 223149 159334 102107 598633
出力例 3
764668547
Score : 525 points
Problem Statement
There is a city represented by a grid with N rows and N columns. The cell at the i-th row from the top and j-th column from the left is denoted as cell (i,j). Each cell has one cafe.
You are planning a meeting. Among the participants, the number of people living in cell (i, j) is (A_i \times B_j) \bmod M. The travel cost for one participant living in cell (s_r,\ s_c) to go to the cafe at cell (t_r,\ t_c) is \max(|s_r - t_r|,\ |s_c - t_c|).
Let f(i, j) be the total travel cost incurred when gathering all the participants at the cafe at cell (i, j).
For each cell (i,j), find the following value, and output the bitwise XOR of these values over all cells.
- f(i,j) + (i-1)N + (j-1)
What is the bitwise XOR operation?
The bitwise XOR of non-negative integers A and B (denoted A \oplus B) is defined as follows.
- The digit in the 2^k's place (k \geq 0) of A \oplus B written in binary is 1 if exactly one of the digits in the 2^k's place of A and B written in binary is 1, and 0 otherwise.
More generally, the bitwise XOR of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \leq N \leq 1500
- 2 \leq M \leq 2 \times 10^6
- 1 \leq A_i \leq M-1 (1 \leq i \leq N)
- 1 \leq B_j \leq M-1 (1 \leq j \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 \dots A_N B_1 \dots B_N
Output
Output the answer.
Sample Input 1
4 19 2 3 1 1 3 4 4 10
Sample Output 1
467
The number of participants living in each cell is as follows: \displaystyle \begin{bmatrix} 6 & 8 & 8 & 1 \\ 9 & 12 & 12 & 11 \\ 3 & 4 & 4 & 10 \\ 3 & 4 & 4 & 10 \end{bmatrix}.
For example, the value of f(1,2) is obtained as the sum 176 of the following 16 values:
- The total amount 6 \times 1 = 6 paid by the 6 residents of cell (1,1), each of whom pays a travel cost of \max(|1 - 1|,\ |1 - 2|) = 1
- The total amount 8 \times 0 = 0 paid by the 8 residents of cell (1,2), each of whom pays a travel cost of \max(|1 - 1|,\ |2 - 2|) = 0
- The total amount 8 \times 1 = 8 paid by the 8 residents of cell (1,3), each of whom pays a travel cost of \max(|1 - 1|,\ |3 - 2|) = 1
- The total amount 1 \times 2 = 2 paid by the 1 resident of cell (1,4), each of whom pays a travel cost of \max(|1 - 1|,\ |4 - 2|) = 2
- \vdots
- The total amount 3 \times 3 = 9 paid by the 3 residents of cell (4,1), each of whom pays a travel cost of \max(|4 - 1|,\ |1 - 2|) = 3
- The total amount 4 \times 3 = 12 paid by the 4 residents of cell (4,2), each of whom pays a travel cost of \max(|4 - 1|,\ |2 - 2|) = 3
- The total amount 4 \times 3 = 12 paid by the 4 residents of cell (4,3), each of whom pays a travel cost of \max(|4 - 1|,\ |3 - 2|) = 3
- The total amount 10 \times 3 = 30 paid by the 10 residents of cell (4,4), each of whom pays a travel cost of \max(|4 - 1|,\ |4 - 2|) = 3
The value of f(i,j) for each cell is as follows: \displaystyle \begin{bmatrix} 220 & 176 & 179 & 224 \\ 199 & 140 & 136 & 182 \\ 212 & 159 & 143 & 178 \\ 255 & 215 & 201 & 218 \end{bmatrix}.
Sample Input 2
6 67 1 6 9 2 3 1 1 10 3 7 2 2
Sample Output 2
1021
Sample Input 3
20 676767 60932 508200 22883 481150 426836 554098 276223 307959 133025 573906 17711 413230 274246 500277 524959 477728 546547 43099 324227 660187 552697 293978 246000 159233 213736 628198 394200 194076 618720 453035 615100 331522 669419 180856 530693 399531 223149 159334 102107 598633
Sample Output 3
764668547