PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Elementary combinatorics
PROBLEM:
An array A of length N is said to be good, if it contains a cyclic subarray of length \frac{N}{2} such that multiplying all the elements of this subarray by -1 results in A having negative sum.
You’re given an N\times N matrix M.
Count the number of good arrays of length N such that:
- 1 \leq A_i \leq N
- M[i][A_i] = 1 for each i.
EXPLANATION:
First, we need to understand the problem itself a bit.
The matrix M given to us essentially tells us which elements can occur at which indices, i.e. if M_{i, j} = 1 then the value j can appear at index i, otherwise it cannot.
Now, let’s analyze when an array can be good.
Suppose we have an array A, and we’re looking at one of its cyclic subarrays of length \frac{N}{2}.
Because the subarray is cyclic, the remaining \frac{N}{2} elements will also form a cyclic subarray.
For example, if A = [1, 4, 2, 5, 4, 6], and we’re looking at the cyclic subarray [2, 5, 4], the remaining elements will form the cyclic subarray [6, 1, 4].
So, we have with us two disjoint cyclic subarrays.
Let their sums be S_1 and S_2.
Now, if S_1 \gt S_2, we can multiply the first subarray by -1, which will result in a sum of S_2 - S_1, which is \lt 0.
Similarly, if S_1 \lt S_2, we can multiply the second subarray by -1 instead to obtain negative sum.
So, the only case where we fail, is if S_1 = S_2.
Note that in the last case, the sum of the entire array must be S_1 + S_2, i.e. each subarray will have a sum equal to half of the full array’s sum.
Observe that what we did above applied to an arbitrary subarray; so an array can only fail to be good if every one of its cyclic subarrays of length \frac{N}{2} has a sum equal to \frac{S}{2}, where S is the sum of the full array.
This is a very powerful condition, because it forces A to be periodic, with a period of \frac{N}{2}.
That is, we’ll have A_i = A_{i+\frac{N}{2}} for every i.
This is very easy to see: compare the subarrays of length \frac{N}{2} starting at index i and index i+1, and they’ll differ only in elements A_i and A_{i+\frac{N}{2}}.
For the subarray sums to be equal, these two elements must be equal.
This condition of being \frac{N}{2}-periodic is not just necessary, but also sufficient for an array to be not good: this is also not hard to see, since any subarray of length \frac{N}{2} will include exactly one of A_i and A_{i+\frac{N}{2}}, and so every subarray will have sum equal to its complement.
This means, to count the number of good arrays, we can instead count the total number of possible arrays, and from that subtract the number of \frac{N}{2}-periodic arrays.
Counting the total number of arrays is quite simple: for each i, the number of possible choices equals the number of ones in the i-th row of the matrix M.
The product of all these counts gives the total number of arrays.
Counting the number of periodic arrays is also not hard: for some i between 1 and \frac{N}{2}, the number of ways in which we can have A_i = A_{i+\frac{N}{2}} equals the number of j such that M_{i, j} and M_{i+\frac{N}{2}, j} are both 1.
The total number of \frac{N}{2}-periodic arrays is once again obtained by just multiplying these counts across all 1 \leq i \leq\frac{N}{2}.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
mod = 10**9 + 7
for _ in range(int(input())):
n = int(input())
m = [input() for i in range(n)]
total = 1
for a in m:
total = total * a.count('1') % mod
bad = 1
for i in range(n//2):
ct = 0
for j in range(n):
ct += m[i][j] == '1' and m[i+n//2][j] == '1'
bad = bad * ct % mod
print((total - bad) % mod)