← 返回题目列表

Codeforces · 2138/E2

E2. 行列式构造(困难版)

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

这是问题的困难版本。版本之间的区别在于,在该版本中,$$$M$$$ 的边长约束较小,而$$$t$$$ 的边长约束较大。只有解决了该问题的所有版本,您才能破解。

给你一个非负整数$$$x$$$。您的任务是构造一个满足以下所有条件的方阵 $$$M$$$:

  • $$$M$$$ 的边长最多为 $$$50$$$。
  • $$$M$$$ 的每个元素是 $$$-1$$$、$$$0$$$ 或 $$$1$$$。
  • $$$M$$$ 的行列式等于 $$$x$$$。
  • $$$M$$$ 的每一行最多可以有 $$$3$$$ 非零位置,$$$M$$$ 的每一列最多可以有 $$$3$$$ 非零位置。

可以证明这样的矩阵总是存在。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含一个整数 $$$x$$$ ($$$0 \le x \le 10^7$$$) — 行列式的目标值。

输出

对于每个测试用例,输出一个整数 $$$n$$$ ($$$1\le n\le 50$$$) 表示方阵 $$$M$$$ 的边长。

然后,输出$$$n$$$行,第$$$i$$$行包含$$$n$$$整数$$$M_{i, 1}, M_{i, 2}, \ldots, M_{i, n}$$$ ($$$M_{i, j} \in \{-1, 0, 1\}$$$),代表矩阵的元素$$$M$$$。

如果有多个矩阵 $$$M$$$ 满足条件,则可以输出其中任何一个。

示例

输入
复制

3
1
2
4

输出
复制

1
1
2
1 -1 
1 1 
5
1 -1 0 0 0 
1 1 1 0 0 
0 1 1 -1 0 
0 0 1 1 -1 
0 0 0 1 1 

注意

请注意,在第三个测试用例中,以下解决方案: $$\begin{pmatrix} 1 & 1 & -1 & 1 \\ -1 & -1 & -1 & 1 \\ 1 & -1 & 0 & -1 \\ 1 & -1 & -1 & -1 \end{pmatrix}$$ 无效,因为矩阵的第一行中有四个非零位置。