K - (mod HW+1)
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 101 点
問題文
整数 H, W, R が与えられます。
H 行 W 列のマス目があり、あなたはすべてのマスに整数を 1 つずつ書き込もうとしています。
上から i 行目、左から j 列目に書き込む整数を P_{i, j} とおくとき、 以下の条件を満たす書き込み方が存在するか判定してください。 もし存在する場合には、そのような書き込み方の一例を求めてください。
-
(P_{1,1}, P_{1,2}, \ldots, P_{1, W}, P_{2, 1}, \ldots, P_{H, W}) は (1, 2, \ldots, H \times W) の並び替えである。
-
どの 2 \times 2 マスを選んでも、その中にある 4 つの整数の積を HW + 1 で割った余りが R に等しい。
- より正確には、任意の 1 \leq i \leq H-1, 1 \leq j \leq W-1 に対し、 P_{i, j} \times P_{i+1, j} \times P_{i, j+1} \times P_{i+1, j+1} \equiv R \pmod{HW + 1} が成立する。
各入力ファイルについて、テストケースを T 個解いてください。
制約
- 1 \leq T \leq 100
- 2 \leq H \leq 50
- 2 \leq W \leq 50
- 0 \leq R \lt HW + 1
- 入力はすべて整数
部分点
この問題の満点は 101 点である。
- 追加の制約 T = 1, H = W = 4, R = 8 を満たすデータセットに正解した場合は 10 点が与えられる。
- 追加の制約 H = W を満たすデータセットに正解した場合は、追加で 90 点(計 100 点)が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
T \mathrm{case}_1 \mathrm{case}_2 \vdots \mathrm{case}_T
各ケースは、次の形式で与えられる。
H W R
出力
条件を満たす書き込み方が存在する場合は Yes
を、存在しない場合は No
を一行目に出力せよ。
さらに、条件を満たす書き込み方が存在する場合は、そのような書き込み方を、続く H 行に次の形式で出力せよ。
P_{1, 1} P_{1, 2} \cdots P_{1, W} P_{2, 1} P_{2, 2} \cdots P_{2, W} \vdots P_{H, 1} P_{H, 2} \cdots P_{H, W}
条件を満たす書き込み方が複数存在する場合、そのどれを出力しても正解となる。
入力例 1
3 2 2 4 5 5 17 6 6 30
出力例 1
Yes 1 2 3 4 No Yes 22 9 31 11 33 32 23 10 2 25 3 19 20 21 8 1 30 13 36 29 16 17 24 7 12 35 27 14 18 34 26 6 28 15 5 4
この入出力例は追加の制約 H = W を満たします。
入力例 2
6 2 3 4 13 11 0 3 8 5 20 24 39 21 3 32 3 13 0
出力例 2
Yes 2 5 4 6 1 3 No Yes 1 19 13 18 14 21 17 22 5 9 10 2 20 16 15 23 7 12 11 4 3 8 24 6 No No Yes 1 2 3 6 7 9 11 13 14 17 18 19 21 5 8 15 16 25 24 35 32 10 4 20 12 30 22 23 26 27 28 29 31 33 34 36 37 38 39