# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

Combinatorics, Inclusion Exclusion, FFT/NTT

# PROBLEM:

Given two positive integers N and M. Let S be the set of all binary grids of dimensions N*M, where the coordinates of the 1's in the grid are strictly increasing.

Let f(T) represent the number of ways to place rooks in the grid T such that, the rooks are non-attacking and no rook is placed in a cell with value 1.

Determine \sum f(t)\mod{998244353}, where t\in S.

# EXPLANATION:

It is immediately obvious that the coordinates of the 1's in each of the generated grids are strictly increasing. Hence, each grid has atmost one 1-valued cell in each row/column.

Let P=\min(N,M). It is also obvious that the maximum number of rooks over all valid arrangements is equal to P.

## Hint 1

Start by finding the number of valid ways to place rooks in a N*M grid consisting of 0's only.

## Solution

Since there are no *unavailable* cells in the grid, we are only concerned with finding the number of different placements such that no two rooks are attacking. This is a classical problem, whose solution can be represented by the formula:

In brief, we count the number of ways to place exactly i rooks (summed over all valid i), by selecting i distinct X and Y coordinates and calculating the number of different sets of coordinates that can be created by pairing these values.

## Hint 2

Now solve for when there is exactly one 1-valued cell in the grid. A little intuition tells us that **the answer is unaffected by the coordinates of the 1-valued cell(s)**.

## Solution

Subtracting the *number of ways to place non-attacking rooks where one rook is placed on the 1-valued cell* **from the** *total number of ways to place non-attacking rooks*, gives us the desired answer.

## How do we calculate the former mentioned value?

The number of ways to place non-attacking rooks on a N*M grid, with the position of one rook fixed, is equivalent to the number of ways to place non-attacking rooks on a (N-1)\cdot(M-1) sized grid (*Why?*)

More formally, let W_i represent the number of ways to place non-attacking rooks on a grid of size (N-i)\cdot(M-i). Then, the answer to the above question is equal to

Can you extend this to solve for when there are i\ (1\le i\le P) 1-valued cells?

## Solution

Standard application of inclusion-exclusion.

The answer is equal to (derivation is mundane and left to the reader as an exercise):

## Hint 3

So far, weâ€™ve derived a method to determine the number of ways we can place rooks when there are exactly 1\le i\le P cells with value 1. Call this value Q_i.

Then, if K_i represents the number of valid grids with *exactly* i 1-valued cells, the answer to the problem is equal to:

How will you calculate array K?

## Solution

By our initial observation (mentioned at the start), the following equation is trivially derivable:

However, we are not done yet. The time complexity of the described solution is O(P^2), which will TLE in the final subtask. Clearly, we need to optimise!

## Analysis (optional, but recommended)

We summarise our progress, along with the time complexity of our approach.

K_i represents the number of valid grids with exactly i, 1-valued cells.

which can be calculated in O(P) with suitable pre computations.

W_i represents the number of ways to place non-attacking rooks on a grid of size (N-i)\cdot(M-i).

and can be computed naively in O(P^2) time.

Q_i represents the number of ways we can place rooks when there are exactly i cells with value 1.

that similarly has an O(P^2) time complexity.

The final answer is then -

The total time complexity is therefore:

## Hint 4

A huge part of our algorithm is devoted to multiplying and summing the values of different arrays (implicitly). This just screams FFT/NTT.

Can you rewrite the above equations to utilise the power of FFT?

## Solution

Letâ€™s start with efficiently calculating array W.

Now, the summation of the products (last term of the equation) can be calculated at once over all i using FFT.

## What are the coefficients of the polynomials to multiply

A=[P!,(P-1)!,\dots,0!] and B=[N!\cdot M!, (N-1)!\cdot (M-1)!, \dots, (N-P)!\cdot (M-P)!]. Let C be the coefficients after multiplying A and B.

Then W_i can be rewritten as:

Which can be computed in O(P\log P + P) overall time complexity.

Similarly, we can rewrite Q_i and apply FFT on it. Deriving the suitable formula is left to the reader as an exercise (you may have to simplify \sum K_i\cdot Q_i and then apply FFT, which is what my solution does). Refer my (well written) code for help.

# TIME COMPLEXITY:

Computing array K takes O(P). Computing array W takes O(P\log P+P). Calculating the final solution takes O(P\log P+P). The final time complexity is therefore:

# SOLUTIONS:

Editorialistâ€™s solution can be found here.

Authorâ€™s solution can be found here.

Testerâ€™s solution can be found here.