what was the idea?

can u please explain the solution of A. I am unable to get (b[i] — a[i] + n) % n , i cant understand it even after looking at the editorial

The idea of the editorial is that:

First, let's try solve the problem without the given m value-1 cells.

How to solve m = 1? If you fill all cells on the antidiagonal with 1, then the sum of any row or column will be 1. No two cells on the antidiagonal are on the same row or column, and each row and each column are contributed by exactly one cell on the antidiagonal. (Assuming 0-based coordinate system is used) Cell v[i][j] on the antidiagonal are those where i + j = n-1. This solves the problem for m = 1.

What if m = 2? First fill the antidiagonal with 1. Then, you can "shift" the antidiagonal by 1 to the left and fill this new "antidiagonal" with 1. This new "antidiagonal" covers all cells v[i][j] where i + j = n-2 and v[n-1][n-1], or equivalently all elements v[i][j] where (i + j) mod n = n-2.

Applying to an arbitrary m, you just need to pick m such "antidiagonal"s and fill cells on them with 1.

How to solve the original problem where m value-1 cells are given? You just need to fill the "antidiagonal" of those m cells first. Some of them might belong to the same "antidiagonal". Then you can fill any rest "antidiagonal"s as needed.

The Editorial of C says:

If $$$v$$$ does not exist or $$$X_v \lt k$$$, the answer is immediately determined as $$$0$$$.

and I forgot to check this case ($$$X_v \lt k$$$) during the contest, but my code got AC.

There is an input for this case:

Input:
10 9
1 2 10
1 3 10
1 4 10
1 5 10
1 6 9
6 7 9
6 8 9
6 9 9
6 10 9
Output:
0

my code during contest will give $$$40320$$$.

There are total of n^2 elements in matrix so each (i-j)%n will occur atmost n times.

(you can draw the matrix of (i-j)%n for some n to see it youself)

since element are occurring on separate row and col we can assign 1 to such element that will increase the sum by n. How many times we need to do this? m times

So at last we just need to select m remainders out of n and assign 1 to those positions.

since some pairs are already given, we can just use remainder of those.

I hope it helps...

Consider solving the subproblem for k, where we convert all p[i] <= k to 0 and p[i] > k to 1. The subproblem is to calculate, after m swaps, the number of (p[i], p[i+1]) such that one of them is 0 and the other is 1. Let s0, s1, s2 represent the states of containing 0, 1, 2 ones in an adjacent pair (p[i], p[i+1]) respectively.

Now, let's consider the transitions of a single swap:

• s0 -> s0, or to say p[i] = 0 and p[i+1] = 0 before and after the swap. There are 3 scenarios:
• • The swap doesn't involve i and i+1. The number of elements except i and i+1 is n-2. The number of swaps of this kind is C(n-2, 2).
• • The swap is (i, j), where p[j] = 0 and j != i+1. There are k zeros in total. Since both p[i] and p[i+1] are zeros, the number of rest zeros is k-2, and thus the number of such swaps is k-2.
• • The swap is (i+1, j), ... Similar to the above case, there are (k-2) such swaps.
• • The swap is just (i, i+1). Ofc the count is 1.
• • In conclusion, the number of swaps turning s0 to s0 is C(n-2, 2) + 2*(k-2) + 1
• s0 -> s1: The swap is (i, j) or (i+1, j), where p[j] = 1. Since the number of ones is (n-k), the number of such swaps is 2 * (n-k).
• s0 -> s2: There's no way to turn 2 zeros to 2 ones in a single swap.

Transitions starting from s2 is just symmetrical to the above transitions starting from s0:

• s2 -> s2: C(n-2, 2) + 2*((n-k)-2) + 1
• s2 -> s1: 2 * k
• s2 -> s0: 0

Transitions starting from s1 can be similarly deducted:

• s1 -> s0: k-1
• s1 -> s1: C(n-2, 2) + (k-1) + ((n-k)-1) + 1
• s1 -> s2: (n-k)-1

With the above transitions, you can construct a 3x3 matrix M, where M[a][b] = the number of ways for the sa -> sb transition in a single swap. Let MM = M^m. Then MM[a][b] = the number of ways for the sa -> sb transition in m swaps. Let S be the 3x1 matrix where S[a][0] = the number of sa states in the original permutation. Let T = MM * S. T[a][0] will be the sum of the number of sa states after all possible m swaps. The answer to the subproblem is T[1][0].