首页 > ACM题库 > HDU-杭电 > hdu 1945 Sylvester construction待解决[解题报告]C++
2013
12-26

hdu 1945 Sylvester construction待解决[解题报告]C++

Sylvester construction

问题描述 :

A Hadamard matrix of order n is an n * n matrix containing only 1s and -1s, called Hn, such that where 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 . 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 ve integers: n, x, y, w and h. n will be between 1 and 2^62 (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 t entirely inside the whole matrix and that 0 < w,h <= 20. There will be no more than 1000 test cases.

输出:

The first number in the input is the number of test cases to follow. For each test case there are ve integers: n, x, y, w and h. n will be between 1 and 2^62 (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 t entirely inside the whole matrix and that 0 < w,h <= 20. There will be no more than 1000 test cases.

样例输入:

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


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?