← 返回题目列表

Codeforces · 1917/E

E. 构造矩阵

中文机器翻译题面 查看原题

给你一个偶数 $$$n$$$ 和一个整数 $$$k$$$。你的任务是构造一个大小为 $$$n \times n$$$ 的矩阵,由数字 $$$0$$$ 和 $$$1$$$ 组成,满足以下条件,或者报告不可能:

- 矩阵中所有数字的总和恰好为$$$k$$$;
- $$$i$$$ 行中所有数字的按位 $$$\texttt{XOR}$$$ 对于每个 $$$i$$$ 都是相同的;
- $$$j$$$ 列中所有数字的按位 $$$\texttt{XOR}$$$ 对于每个 $$$j$$$ 都是相同的。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 130$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例由一行描述,其中包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 1000$$$,$$$n$$$ 是偶数,$$$0 \leq k \leq n^2$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,如果可以构造满足所有问题条件的矩阵,则输出 $$$\texttt{Yes}$$$,否则输出 $$$\texttt{No}$$$。

如果可以构造一个矩阵,则接下来的 $$$n$$$ 行的第 $$$i$$$ 行应包含表示矩阵第 $$$i$$$ 行中元素的 $$$n$$$ 整数。

示例

输入 #1

5
4 0
6 6
6 5
4 2
6 36

输出 #1

Yes
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Yes
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
No
No
Yes
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

注意

在第一个示例中,满足所有条件:

- 矩阵中所有数字的总和恰好为$$$0$$$;
- 对于每个 $$$i$$$,$$$i$$$ 行中所有数字的按位 $$$\texttt{XOR}$$$ 为 $$$0$$$;
- 对于每个 $$$j$$$,$$$j$$$ 列中所有数字的按位 $$$\texttt{XOR}$$$ 为 $$$0$$$。

在第三个例子中,可以证明不可能找到满足所有问题条件的矩阵。