同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21893_SylvesterConstruction

2022-5-16 18:20| 发布者: Hocassian| 查看: 29| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505936972300-Problem List-采集的数据-后羿采集器.html

Pro.ID

21893

Title

Sylvester Construction

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21893

AC

Submit

Ratio

时间&空间限制

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

A Hadamard matrix of order n is an n * n matrix containing only 1s and -1s, called H_n , such that H_n H_n^T = nI_n where I_n is the n * n identity matrix. An interesting property of Hadamard matrices is that they have the maximum possible determinant of any n * n matrix with elements in the range [-1, 1]. Hadamard matrices have applications in errorcorrecting codes and weighing design problems.

The Sylvester construction is a way to create a Hadamard matrix of size 2n given H_n . H_2n can be constructed as:

For example:

and so on.

In this problem you are required to print a part of a Hadamard matrix constructed in the way described above.

输入

The first number in the input is the number of test cases to follow. For each test case there are five integers: n, x, y, w and h. n will be between 1 and 2⁶² (inclusive) and will be a power of 2. x and y specify the upper left corner of the sub matrix to be printed, w and h specify the width and height respectively. Coordinates are zero based, so 0 <= x, y < n. You can assume that the sub matrix will fit entirely inside the whole matrix and that 0 < w, h <= 20. There will be no more than 1000 test cases.

输出

Description

The Sylvester construction is a way to create a Hadamard matrix of size 2n given H_n . H_2n can be constructed as:

For example:

and so on.

In this problem you are required to print a part of a Hadamard matrix constructed in the way described above.

Input

Output

For each test case print the sub matrix followed by an empty line.

Sample Input

3
2 0 0 2 2
4 1 1 3 3
268435456 12345 67890 11 12

Sample Output

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 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 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 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 -1

Source

Norgesmesterskapet i Programmering 2004

样例输入

3
2 0 0 2 2
4 1 1 3 3
268435456 12345 67890 11 12

样例输出

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 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 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 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 -1