~1 minutes left

F is not counting anyway.

The swappable rows and cols are independent of each other. Both build components. In each component there are factorial(componentSize) permutations. Multiply all of them.

Which rows and cols are swappable can be found by brute force in O(n^3)

For the columns, you count the number of connected components (I use a dsu for this). Do the same for the rows. Now count the number of permutations for each component. The answer is the product of all those numbers.

Basically solve independently for rows and columns and multiply the answer for both of them.

Make a network where i,j is connected if rows i and j can be exchanged. Now the answer is the multiplication of the factorial of the size of each connected component(since size! ways to arrange these components).

Do the same for columns.

Reference link — link

Observe that switching rows has no effect on columns that you can switch, and vice versa. So now, the switching of rows and columns is independent of one another. Now we just need to find which rows we can switch ($$$O(n^3)$$$). The number of ways we could arrange these rows is $$$m!$$$ for each group of size $$$m$$$ that we can switch (By group I mean a set of rows that we can arrange in any order). We can find each of these groups with DSU. Do the same for columns, and multiply for your answer

For D use DP approach.

Initially lets start with k ones. Now we have to make n-k further breakdowns to have n elements. Each breakdown will result in two numbers with values half of the breakdown element. (For eg, If we decide to break down 4 1/2 elements, we will have 8 1/4 elements)

Now lets breakdown in descending order starting from 1. (ie break some 1's -> break some 1/2's ->break some 1/4's and so on)

Its now a n^3 dp with states as the breakdowns left(to have total n elements in the array and we initially start with k elements) and the amount of the latest value elements we have after the breakdown in the last step. This could be reduced to n^2 by prefix sums.

Reference solution — link

Try to brute force the first 100 rows and columns,try to find the regular pattern.

Did you notice the constraints? a <= 1e9. Isn't it obvious you got TLE? No tricks in implementation, rather you should have realized this TLE issue, and come up with some math solution that works in O(1).

Observe that $$$a,b,c \geq 10^9$$$. It will definitely TLE. Try to think of reducing this sum (product??) with math.

For B rewrite the equation as $$$(A + B) - (C + D) = k$$$
Loop through all possible values of $$$(A + B)$$$ and calculate how many pairs($$$1 <= a <= n$$$, $$$1 <= b <= n$$$) can form $$$(A + B)$$$ same for $$$(A + B) - k$$$ = $$$(C + D)$$$ and multiply the both
Submission: Link

And nothing will happen to your rating

My proof contains a bit of cases but is overall quite clean.

Let us show four facts (true for cells with indexes $$$\ge 5$$$):

1) The configuration x x does not occur. This follows directly from the statement.

2) The configuration 2 1 2 does not occur. Indeed, it would generate

? 0 0
2 1 2

but we have already established that 0 0 cannot occur.

3) The configuration 1 2 1 does not occur. Indeed, it would generate

? 0 0
1 2 1

but we have already established that 0 0 cannot occur.

4) The configuration 0 2 0 does not occur. Indeed, it would generate

2 1 2
0 2 0

but we have already established that 2 1 2 cannot occur.

Now that we have these four facts, consider three consecutive cells x y z. It holds $$$y\not= x$$$ and $$$y\not=z$$$.

1. If $$$y=0$$$ then $$$y=mex(x, z)$$$.
2. If $$$y=1$$$ then either $$$y=mex(x, z)$$$ or $$$x=z=2$$$ which is impossible.
3. If $$$y=2$$$ then either $$$y=mex(x, z)$$$ or $$$x=z=0$$$ which is impossible or $$$x=z=1$$$ which is impossible.

Thus we have proven that $$$y=mex(x,z)$$$. As a consequence (by induction on the indices) we get

Hence we have shown $$$a(i,j) = a(i-1,j-1)$$$ for any $$$i,j$$$ large enough ($$$i,j\ge 5$$$ should be enough).

$$$k>n$$$ is zero.

Say among four columns A, B, C and D, you can swap pairs (A, B), (A, C) and pairs (C, D), so all of these form a single component.

We can achieve all orderings by an order of swaps. Starting from ABCD, to get BDAC, we make swaps to get ABCD -> BACD-> BCAD-> BDAC, to get CBDA, we follow ABCD-> ABDC-> CBDA.

We can see that for a pair(x, y), we can achieve this swaps through a sequence of swaps, if x and y lie in same connected component. Visualize like moving on a path over spanning tree formed by these edges (pairs).

let's denote the transposition of positions i and j by (i j).

then (A C) = (A B)*(B C)*(A B) (* denotes the function composition)

it's easy to prove inductively that in order to generate the entire permutations, you only need N-1 transpositions forming a spanning tree, using the above equality.

(this is also one of the basic exercise you'll find in any group theory course)

This overflows because you multiplicate three multiplicators, then use the mod operation. Since the mod value is at about 2^30 that would require the integer type to be about 90 bit. Use instead something like cout<<((((s1%mod)*(s2%mod))%mod)*(s3%mod))%mod; multiplication one value at a time.

For context, the editorial of problem B says that it can also be solved using "inclusion-excusion and so on" in $$$O(1)$$$. Would be great if someone could briefly explain the approach.