PerfectSquare
SRM 620 · 2013-12-22 · by cgy4ever
Problem Statement
There is an n by n matrix of positive integers.
You are given its elements in a
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.
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.
{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
Submissions are judged against all 105 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PerfectSquare with a public method int ways(vector<int> x) · 105 test cases · 2 s / 256 MB per case