RooksParty
SRM 473 · 2009-11-12 · by misof
Problem Statement
The black and white chess rooks were bored, so they decided to invite their colorful friends to a party. However, as the evening progressed, many pairs of rooks of different colors started arguing and threatening each other.
To prevent a massacre, you now need to place all the rooks in such a way that no two rooks of different colors attack each other.
You are given the dimensions of the chessboard:
Compute and return the value (X mod 1,000,000,009), where X is the number of valid arrangements of all the given rooks on the given chessboard. No square of the chessboard may contain more than one rook. Rooks of the same color are undistinguishable.
Notes
- Two rooks attack each other if they are either in the same row or in the same column, and all squares between them are empty.
Constraints
- rows will be between 1 and 30, inclusive.
- columns will be between 1 and 30, inclusive.
- counts will contain between 1 and 10 elements, inclusive.
- Each element of counts will be positive.
- The sum of all elements of counts will not exceed rows*columns.
2
3
{1,1}
Returns: 12
Here are all 12 valid placements: 1.. 1.. .1. .1. ..1 ..1 .2. ..2 2.. ..2 2.. .2. .2. ..2 2.. ..2 2.. .2. 1.. 1.. .1. .1. ..1 ..1
5
2
{3}
Returns: 120
As all three rooks have the same color, we can put them on any three squares.
5
2
{1,1,1}
Returns: 0
It is impossible to place these rooks correctly.
8
8
{1,1,1,1,1,1,1,1}
Returns: 625702391
Here the answer is (8! * 8!) modulo 1,000,000,009.
8
8
{2,2,2,2}
Returns: 394476764
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RooksParty with a public method int countArrangements(int rows, int columns, vector<int> counts) · 116 test cases · 2 s / 256 MB per case