题目详情题解（0）讨论（0）提交记录（0）

AT_tupc2023_k.(mod HW+1)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定整数 H,W,RH, W, R。

有一个 HH 行 WW 列的格子，你需要在每个格子中写入一个整数。

令第 ii 行第 jj 列写入的整数为 Pi,jP_{i, j}，请判断是否存在一种写法，使得如下条件成立。如果存在，请给出一种这样的写法。

  • (P1,1,P1,2,…,P1,W,P2,1,…,PH,W)(P_{1,1}, P_{1,2}, \ldots, P_{1, W}, P_{2, 1}, \ldots, P_{H, W}) 是 1,2,…,H×W1, 2, \ldots, H \times W 的一个排列。

  • 任意选择一个 2×22 \times 2 的小方格，其包含的 44 个整数的乘积除以 HW+1HW + 1 的余数恰好等于 RR。

    • 更准确地说，对于任意 1≤i≤H−1,1≤j≤W−11 \leq i \leq H-1, 1 \leq j \leq W-1，都有：Pi,j×Pi+1,j×Pi,j+1×Pi+1,j+1≡R(modHW+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}。

对于每个输入文件，需要解答 TT 个测试用例。

输入格式

输入以如下格式从标准输入读入。

T case1 case2 ⋮ caseTT\ \mathrm{case}_1\ \mathrm{case}_2\ \vdots\ \mathrm{case}_T

每个测试用例的格式如下：

H W RH\ W\ R

输出格式

如果存在满足条件的写法，首行输出 Yes，否则输出 No。

如果存在，接下来的 HH 行输出其中一种方案。每行 WW 个整数，具体格式为：

P1,1 P1,2 ⋯ P1,WP_{1, 1}\ P_{1, 2}\ \cdots\ P_{1, W}

P2,1 P2,2 ⋯ P2,WP_{2, 1}\ P_{2, 2}\ \cdots\ P_{2, W}

⋮\vdots

PH,1 PH,2 ⋯ PH,WP_{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

  • 输入#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

说明/提示

部分分

本题满分为 101101 分。

  • 如果你能解决满足 T=1,H=W=4,R=8T = 1, H = W = 4, R = 8 的数据，可以获得 1010 分。
  • 如果你能解决满足 H=WH = W 的数据，可以额外获得 9090 分（共 100100 分）。

样例解释 1

本组输入输出满足额外条件 H=WH = W。

数据范围

  • 1≤T≤1001 \leq T \leq 100
  • 2≤H≤502 \leq H \leq 50
  • 2≤W≤502 \leq W \leq 50
  • 0≤R<HW+10 \leq R < HW + 1
  • 所有输入均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页