PerfectSquare | Topcoder Archive

Problem Statement

There is an n by n matrix of positive integers. You are given its elements in a int[] x with n*n elements. For each i and j (0-based indices), the number in row i, column j of the matrix is x[i*n+j].

You want to select some elements of the matrix. Your selection must satisfy the following constraints:

Each row must contain an odd number of selected elements.
Each column must contain an odd number of selected elements.
The product of all selected elements must be a perfect square.

Return the number of valid ways to select such subset of elements, modulo 1,000,000,007.

Definition

Class:: PerfectSquare
Method:: ways
Parameters:: int[]
Returns:: int
Method signature:: int ways(int[] x)
(be sure your method is public)

Constraints

n will be between 1 and 20, inclusive.
x will contain exactly n*n elements.
Each element in x will be between 1 and 1,000,000,000, inclusive.

Examples

```
{1, 1,
 1, 2}
```
```
Returns: 1
```
The only valid solution is to select the elements in the cells (0,1) and (1,0). Their product is 1 = 1^2.
```
{620, 620,
 620, 620}
```
```
Returns: 2
```
Two solutions: {(0,0), (1,1)}, {(0,1), (1,0)}.
```
{1, 2, 3,
 4, 5, 6,
 7, 8, 9}
```
```
Returns: 1
```
The only valid solution is to select the elements with values 1, 2, 3, 6, and 9. Their product is 1*2*3*6*9 = 324 = 18^2.
```
{2, 2, 2, 2, 2,
 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2,
 2, 2, 2, 2, 2}
```
```
Returns: 0
```
In this test case the total number of selected elements will always be odd. Thus, the product of all selected elements will always be equal to 2^(2k+1) for some k. A number of the form 2^(2k+1) can never be a perfect square.

{2, 3, 4, 5,
 6, 7, 8, 9,
 10,11,12,13,
 14,15,16,17}

Returns: 4

{9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,
 9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,
 9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,
 9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,
 9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,
 9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,
 9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,
 9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,
 9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,
 9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690,9699690}

Returns: 993282280

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.