May 8, 2015
SRM 657
DURATION
30 mincategories
Tags
share
Match Summary
Round Overview
Discuss this match
All that we need to do is count the number of rooks in each row and in each column. If for any row or column, the number of rooks is different to 1, then the setup is incorrect.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
string isCorrect(vector < string > board) {
const int n = 8;
for (int i = 0; i < n; i++) {
int r = 0;
int c = 0;
for (int j = 0; j < n; j++) {
// Count rooks in row i:
if (board[i][j] == 'R') {
r++;
}
// Count rooks in column i:
if (board[j][i] == 'R') {
c++;
}
}
if (r != 1 || c != 1) {
return "Incorrect";
}
}
return "Correct";
}
ProblemSetsEasy
Problem Details
The problem is the same as the division 1 version but with smaller constraints. The difference is that you can do the same analysis as in division 1 but binary search is not needed, so we can just use a simple linear search for the largest x:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
long allowedX(long E, long EM, long M, long MH, long H, long x) {
if (E + EM < x) {
return false;
}
long aa = std::min(EM, E + EM - x); //maximum a
if (H + MH < x) {
return false;
}
long bb = std::min(MH, H + MH - x); //maximum b
return (M + aa + bb >= x);
}
int maxSets(int E, int EM, int M, int MH, int H) {
int res = 0;
for (int x = 1; x <= MH + H; x++) {
if (allowedX(E, EM, M, MH, H, x)) {
res = x;
}
}
return res;
}
Two decisions are involved in this problem:
Of the EM problems that can be easy or medium, how many will be assigned as medium? Let that number be `a`
Of the MH problems that can be medium or hard, how many will be assigned as medium? Let that number be `b`
When `a` and `b` are known, we can calculate the number of problems of each difficulty we have available:
`E + (“EM” - a) ` easy problems.
`M + a + b` medium problems.
`H + (“MH” - b) ` hard problems.
To have a problem set we need one of each kind of problems, so the maximum problem sets is `min(E + “EM” - a, M + a + b, H + “MH” - b)`.
Imagine we wanted to see if it is possible to have `x` problems in total:
If `E + “EM” < x`, no matter what value of `a` we pick, the number of easy problems would be too small.
If `E + “EM” >= x`, then there are normally enough easy problems unless `a` becomes too large. We can find the maximum allowed value of `a`: `M_a = x - E + “EM”`. Also `a` cannot be larger than `“EM”`
Similarly, `H + “MH”` must be at least `x` and `M_b = x - H - “MH”` is the maximum allowed value for `b`.
We just need `M + a + b` to be at least `x`, imagine we take the maximum allowed values: if `M + M_a + M_b >= x` then we can know `x` is a valid number of problem sets
Now note that if a value of `x` is allowed, then so will all smaller values and if a value of `x` is not allowed , no value larger than `x` will be allowed. So we can use Binary Search to find the maximum allowed value for `x`, this is the maximum possible number of problem sets.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
long allowedX(long E, long EM, long M, long MH, long H, long x) {
if (E + EM < x) {
return false;
}
long aa = std::min(EM, E + EM - x); //maximum a
if (H + MH < x) {
return false;
}
long bb = std::min(MH, H + MH - x); //maximum b
return (M + aa + bb >= x);
}
long maxSets(long E, long EM, long M, long MH, long H) {
// We have to maximize:
// min(E + EM - a, M + a + b, H + MH - b)
// where 0 <= a <= EM , 0 <= b <= MH
long lo = 0; // we know 0 is allowed
long hi = M + MH + 1; // we know this will never be allowed
while (lo + 1 < hi) {
long x = (lo + hi) / 2;
if (allowedX(E, EM, M, MH, H, x)) {
lo = x;
} else {
hi = x;
}
}
return lo;
}
PolynomialRemainder
Problem Details
We are given a modular congruence of the type:
`ax^2 + bx + c -= 0 mod 10^9`
How man we solve this? One way would be to try `x = 0 , … 999999999` until we find a solution. This might be too slow because evaluating the modular result `10^9` times is too much. It would definitely be a good enough solution if the modulo was smaller.
Chinese Remainder Theorem
This is what makes the CRT a very useful tool in this case. With that we can find the solution to `ax^2 + bx + c -= 0 mod (A*B)` by solving two other congruences:
`ax^2 + bx + c -= 0 mod A`
`ax^2 + bx + c -= 0 mod B`
Assuming `gcd(A,B) = 1`.
This becoms clearer when we factorize `10^9 = 2^9 * 5^9`. `gcd(29,59) = 1`, meaning these two factors of `10^9` are pairwise coprime. This means that we can find the solution to the large congruence by first solving:
`ax^2 + bx + c -= 0 mod 2^9`
`ax^2 + bx + c -= 0 mod 5^9`
This is very useful because `2^9 = 512` and `5^9 = 1953125`, now we need to evaluate the formula at most `512 + 1953125` times, by findng a solution `x` for each of the two equations. We will have two solutions `x_2` and `x_5` such that:
`x -= x_2 mod 2^9`
`x -= x_5 mod 5^9`
We can use this new knowledge about `x` to find a value modulo `10^9`. We just need to find a number from 0 to `999999999` such that it is equal to `x_2` modulo `2^9` and `x_5` modulo `5^9`. There are only `2^9` integers in the range that are equal to `x_5` modulo `5^9` (Divide `10^9` by `5^9`). So we can try all of those integers and check if any if equal to `x_2` modulo `2^9`.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// solve modular quadratic equation for a given modulo m:
int findRootMod(int a, int b, int c, int m) {
for (int i = 0; i < m; i++) {
// manuallly multiply, using properties of modular arithmetic
long x = i;
long p = (a * (x * x % m)) % m;
long q = (b * x) % m;
long r = c;
// if the result is 0 modulo m, we have a result.
if ((p + q + r) % m == 0) {
return i;
}
}
return -1;
}
int findRoot(int a, int b, int c) {
const int POW2 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2;
const int POW5 = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5;
int x2 = findRootMod(a, b, c, POW2);
int x5 = findRootMod(a, b, c, POW5);
if (x2 == -1 || x5 == -1) {
return -1;
}
// try all values of x = x5 modulo POW5:
int x = x5;
while (x % POW2 != x2) {
x += POW5;
}
return x;
}
Prime numbers
Consider the prime factorization of the GCD, it will be a product of some prime numbers each raised to some power. Consider the following question for a fixed prime number `p`: Will the polynomial always be divisible by `p`? Since `p` is prime, this means that regardless of the value of `x`, at least one of the factors `(x-i)^s_i` must be divisible by `p`. For `(x-i)^s_i` to be a multiple of `p`, we need `(x-i)` to be a multiple of `p`. Therefore, at least one `(x-i)` must be a multiple of `p`. With help from modular arithmetic we have that `x -= i mod p`. For all values of `x`, at least one `i` must exist such that `x -= i mod p`. If this is true for `x = 0,1,2,…p-1`, it should be true for all `x`. Because one of the values is `p-1`, there must be at least one `i -= p-1 mod p`. With this we can conclude that `p` cannot exceed `n`. So we only need to consider the `O(n)` prime numbers between 2 and `n`.
Prime exponents
For a prime `p`, we need to find the maximum exponent `e_p` such that `p^(e_p)` will divide the polynomial for any given `x`. This is the most theory-heavy part of the problem.
Imagine we fixed `x`. Let’s find, for polynomial `P(x)`, the maximum exponent `k_x` such that `P(x)` is divisible by `k_x`. `p` is prime, so we can first treat each `(x - i)^(s_i)` separately. Find the maximum exponent `b_i` such that `(x - i)` is divisible by `p^b`, then we have `a = b_i s_i`. `k_x` is the sum of all `b_i s_i` for each `i`. This is the maximum exponent for `p` that will divide the polynomial `P(x)`. Note that if `(x-i)` is not a multiple of `p`, the exponent will be 0.
What is the exponent that is guaranteed to divide for any value of `x`, imagine for every possible `x` we found `k_x`, if we find the minimum `k_x` and name it `r`, then we can state that for any `x`, `P(x)` will divide `p^r`, it may be able to also divide larger exponents, but `r` is the guaranteed one, the minimum between every `x`.
For example, `x(x-1)^9(x-2)` and `p = 2`:
For `x = 0`, we need to consider `x` and `(x-2)`, for `x`, the result is 0, this means that any exponent `a` for `p^a` will work. The result is … infinite. This shall be our first speed bump. But since we want the minimum result, we can ignore these infinite results. There will be an infinite result for all cases where `x - i = 0`. Let’s skip to `x = p+1`.
For `x = 3`, we consider factors where `x -= i mod p`, so we have `(x-1)^9`, `x-1 = 2`, the maximum exponent is 1. Multiplied by 9 we get 9. This means that `(x-1)^9` is divisible by `2^9`. The total exponent sum for `x = 3` is 9.
For `x = 4`: `x = 4` and `(x-2) = 2`, the exponents are 2 and 1, respectively, the sum is 3.
For `x = 5`, `(x-1)^9 = 4^9 = 2^18`, the total sum is 18.
For `x = 6`, `x(x-2) = 6*4`, the exponents are 1 and 2, the sum is 3.
For `x = 7`, `(x-1)^9`, 9 again.
We will discover a cyclic nature: 9,3,18,3,9,3,18,3… Apart of the 3 infinite results, all other results will be 9,3 or 18. The minimum is 3. Ergo `2^3` is guaranteed to divide `P(X)`, but not `2^4`. So we only need to simulate some few of the values of `x` and we will have enough representatives to find the minimum for all `x`.
The cycle length is 4. Why? It comes to mind that `p^2 = 4`. With any other example, it would seem that the length is `p^m` where `m` is the maximum integer such that `p^m <= n`. I deliberately picked a case that shows this idea is wrong. The answer is to pick the maximum `m` such that `p^m <= 2n`, but this might be difficult to prove without knowledge of another approach.
A distinct approach
From the ideas in the previous section we can come up with a new approach that doesn’t have those pitfalls and can be implemented as an algorithm with a relatively low time complexity.
Imagine a case: “19283”, polynomial: `P(x) = x(x-1)9(x-2)2(x-3)8(x-4)3`. We want to find the minimum possible exponent of `p = 2` that divides `P(x)` no matter the value of `x`.
There are 2 possibilities:
`x` is even. Which means that `x`, `x-2` and `x-4` are even. So, `x`, `x-2` and `x-4` will divide at least `p^1`, maybe they can divide a larger power of `p`, but we will care about that later. For now we can use the exponents: `1 + 2 + 3` and add them to the sum of exponents , so we know `P(x)` will divide at least `p ^ 6`. But maybe some of these multiples of 2 will also be multiples of 4. In fact, there are two possibilities, because every two multiples of `2` we will have a multiple of `4`.
`x-2` is a multiple of 4. This means we will add exponent `2` to the result. Therefore `P(x)` divides at least `p^8`.
`x` and `x-4` are multiples of 4. This means that we will have to add more exponents: `1 + 3`. `P(x)` divides at least `p^10`. But something interesting: One of `x` or `x-4` might be a multiple of 8.
If it is `x`, the exponent increases by `1`.
If it is `x-4`, the exponent increases by `3`.
If `x` is odd, then `x-1` and `x-3` are even. Their exponents are `9 + 8`.
Either `x-1` is a multiple of 4, which adds `9` to the final exponent.
Or `x-3` is a multiple of 4, adds `8`.
This is the crucial part. If we analyze this all we have that the final exponent is: `min(1+2+3 + min(1+3 + min(1,3), 2), 9+8+min(9,8))`.
This is a very useful recursive approach. For `F(s)` , where `s` are the exponents of `x,x-1,x-2,…` :
If `len(s) < p`, then in the worst case, none of the factors will be a multiple of `p`, the result is 0.
Else we split the string of exponents in `len(s) / p` parts: `X_1 = s[0]s[p]s[2p]…, X_2 = s[1]s[p+1][p+2]… , …` then the result is equal to: `min( s[0] + s[p] + s[2p] + … + f(s[0]s[p]s[2p]), s[1] + s[1+p] + s[1+2p] … + f(s[1]s[1+p]s[1+2p]), …)` Note how we split the string in distinct strings each starting with a different index and skipping by `1`, we calculate the sum of the powers and then reduce the remaining exponent to reusing the function but for the split string.
A complexity analysis: First of all, when splitting the string, each index of the string is used exactly once in each different partition of the string. This means that we need `O(n)` time to create each partition and call `f()` on the smaller strings. Whenever we call a new instance of `f()`, the size of the original string is divided by `p`, hence the depth will be of logarithmic size. Note that in each depth of the string, we see each `s[i]` exactly once. Hence the complexity is `O(log(n) n)`. This is something we repeat for each prime number up to `n`. So the total complexity is `O(n^2 log(n))`
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const int MOD = 1000000007;
list < int > getPrimes(int n) {
list < int > primes;
vector < bool > iscomposite(n + 1, false);
for (int p = 2; p <= n; p++) {
if (!iscomposite[p]) {
for (int i = p + p; i <= n; i += p) {
iscomposite[i] = true;
}
primes.push_back(p);
}
}
return primes;
}
// the recursive part, get n/p partitions each skipping by p
int minExp(string s, int p) {
if (s.size() < p) {
return 0;
}
int resminexp = 1000000000;
for (int i = 0; i < p; i++) {
string r = "";
int x = 0;
for (int j = i; j < s.size(); j += p) {
x += s[j] - '0';
r += s[j];
}
resminexp = std::min(resminexp, x + minExp(r, p));
}
return resminexp;
}
int gcd(string s) {
int n = s.size();
cout << "n = " << n << endl;
long res = 1;
for (int p: getPrimes(n)) {
for (int i = minExp(s, p); i >= 1; i--) {
res = (res * p) % MOD;
}
}
return (int)(res % MOD);
}
Equivalent squares
The input can be seen as a graph in which rooks `i` and `j` are connected if and only if `graph[i][j]=1`. A decent strategy seems to be placing the rooks one by one, counting how many ways you have to place the remaining rooks after each rook placement. Of course, a simple backtracking implementation would easily time out, there are too many possibilities. However, let’s suppose we try to follow this strategy and look at what happens.
The first rook can be placed in any of the `N^2` squares. However, one might notice that if we take a placement that satisfies all the requirements, swapping two columns or rows we obtain a solution that still satisfies all the requirements! This allows for a simple bijection argument that lets us conclude that the number of possibilities for any of those `N^2` choices is actually the same. Here’s how: let’s compare the number of solutions in which rook 0 occupies square `(a,b)` and the number of solutions in which it occupies `(c,d)`. For each solution in which rook 0 occupies square `(a,b)`, we can swap rows `a` and `c`, and columns `b` and `d` to get a solution in which rook 0 occupies square `(c,d)`. Using the same strategy, we can get a solution in which the rook occupies `(a,b)` from a solution in which it originally occupied `(c,d)`. This proves there is a one-to-one correspondence between these two sets of solutions, and therefore the number of solutions of each type must be the same.
This shows that we can just place the first rook anywhere, and we can then multiply the final answer by `N^2`. For simplicity, let’s place it on the top-left corner of the board, square `(0,0)`. Now name `A` the first rook for which `graph[0][A]=1`, this rook must lie either on the same row or column of rook 0. We can try both possibilities. Suppose we pick the same column. By the swapping observation, all of the rows to choose are equivalent and produce the same number of solutions, so we might as well pick any of them and correct the answer later.
For the remaining rooks connected to group 0, which of them go in the same row and which go in the same column? Let’s remember we also have the other rows of `graph` to look at: groups of rooks on the same line are all connected to each other. This allows us to split the rooks connected to rook 0 in two groups of connected rooks: one of these groups is on the same line as `A`, the other is not. If there are more than two groups, it’s impossible to place them satisfying the conditions. Which of the groups goes in the row and which goes in the column depends on where we placed `A` earlier.
We can use the swap idea again: suppose group 1 goes in the column of rook 0. On which rows will we place the rooks? Any placement will lead to the exact same number of resulting solutions, because we can swap rows until we get the placement we want. This means we can place all rooks in a convenient manner, then multiply by the number of possibilities of choosing their rows. In the editorial implementation, the rooks are placed in increasing rows for simplicity.
Successive deductions
We have now placed some rooks in the row / column of rook 0. These rooks also have rooks that are connected to them; suppose a rook `j` that has not been placed yet is connected to a rook `i` that is in the same row as rook 0. This means that `i` and `j` are necessarily in the same column: `j` can’t be in the same row as rook 0, otherwise we would have placed it already. If `j` also is connected to one of the existing rooks in the same column as rook 0, we already know where `j` is; otherwise, `j` must occupy a row that has no rooks yet. The swapping observation tells us once more it doesn’t make a difference which one we pick; we might as well pick the first, then multiply by the number of possibilities.
We can continue this reasoning for all rooks we place. For instance, any rooks connected to `j` that are not connected to `i` must be in the same row as `j`, and so on. If we do this for all rooks we place, we will end up eliminating a whole connected component from the graph. The remaining rooks have to placed on the remaining empty rows and columns, so we can remove occupied rows and columns from the board, as well as already placed rooks from the graph, and call our counting function recursively. Of course, we might eliminate a different number of rows and columns: the original board was always square, but now we have to support rectangular boards as well.
Wrapping up
We have a procedure `F(nRows, nCols, graph)` that counts the number of ways to place the rooks in a rectangular board by eliminating the connected component of the graph that contains rook 0, then calling itself recursively. If we implement this as a backtrack, it’s still too slow.
However, we’re almost there, and this can work if we implement `F` a little differently. Note that the function always eliminates the connected component containing rook 0. This means the sequence of graphs our function will process is always the same, and each of these graphs has more rooks than the next.
Maybe we can get away with precomputing interesting things about this sequence of graphs. The choices we had to make were all about picking unoccupied rows or columns. Let `colSize[n]` be, for the graph with `n` rooks, the number of rooks that had to choose a new column if `A` occupies the same column as rook 0. Let `rowSize[n]` be, for the graph with `n` rooks, the number of rooks that had to choose a new row if `A` occupies the same column as rook 0. Finally, let `nxtGraph[n]` be the next graph of the sequence after the graph with `n` rooks. Since there are at most `R` graphs in the sequence, where `R` is the number of rooks, and we can process each graph in `O(R^2)`, we can precompute these arrays in `O(R^3)`.
We have two possibilities for the transition:
if we place rook `A` in the same column as rook 0, we have `C(nCols, colSize[n]) * (colSize[n])!` possibilies to choose the unoccupied columns, `C(nRows, rowSize[n]) * (rowSize[n])!` possibilities for the unoccupied rows, and `F(nCols - colSize[n], nRows - rowSize[n], nxtGraph[n])` for the remaining rooks.
If we place rook `A` in the same row as rook 0, we have `C(nCols, rowSize[n]) * (rowSize[n])!` possibilies to choose the unoccupied columns, `C(nRows, colSize[n]) * (colSize[n])!` possibilities for the unoccupied rows, and `F(nCols - rowSize[n], nRows - colSize[n], nxtGraph[n])` for the remaining rooks.
If we remember that there are at most `R` graphs we can choose, the `F` function will be called with at most `O(N^2R)` different argument triplets. This means that memoization can come to the rescue. The transition can be made in `O(1)`, leading to a complexity of `O(N^2R)` for the `F` function. This leads to an algorithm with overall complexity `O(R^3 + N^2R)`, which should be more than fast enough to fit within the time limit.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
int C[60][60];
long long fac[60];
const int mod = 1000000007;
pair < int, int > placed[60];
int pd[60][60][60];
int calc[60];
int colSizes[60];
int rowSizes[60];
vector < string > remGraphs[60];
bool ok = true;
char intersect(pair < int, int > a, pair < int, int > b) {
return '0' + (a.first == b.first || a.second == b.second);
}
int solve(int Ncol, int Nrow, vector < string > & graph) {
if (!ok) return 0;
int num_rooks = graph.sz;
int n = num_rooks;
if (Ncol < 0 || Nrow < 0) return 0;
if (num_rooks == 0) return 1;
if (Ncol == 0 || Nrow == 0) return 0;
// If this is the first time we reached this graph size,
// compute number of "group 1" rooks, number of "group 2" rooks and next graph size
if (!calc[num_rooks]) {
for (int i = 0; i < num_rooks; i++) {
placed[i] = make_pair(-1, -1);
}
placed[0] = make_pair(0, 0);
vector < int > columnRooks, rowRooks;
int columns_placed = 0, rows_placed = 0;
// Detect "group 1" and "group 2"
for (int i = 1; i < n; i++) {
if (graph[0][i] == '1') {
for (int j = i; j < n; j++) {
if (graph[0][j] == '1' && graph[i][j] == '1') {
columnRooks.push_back(j);
placed[j] = make_pair(0, columnRooks.size());
}
}
break;
}
}
for (int i = 1; i < n; i++) {
if (graph[0][i] == '1' && placed[i].first == -1) {
for (int j = i; j < n; j++) {
if (graph[0][j] == '1' && graph[i][j] == '1') {
rowRooks.push_back(j);
placed[j] = make_pair(rowRooks.size(), 0);
}
}
break;
}
}
// For each rook we placed, look at which deductions we can make from it
while (columns_placed < columnRooks.sz || rows_placed < rowRooks.sz) {
if (columns_placed < columnRooks.sz) {
int th = columnRooks[columns_placed];
vector < int > newRows;
for (int i = 0; i < n; i++) {
if (placed[i].first == -1 && graph[i][th] == '1') {
bool found = false;
for (int j: rowRooks) {
if (graph[j][i] == '1') {
found = true;
placed[i] = make_pair(placed[j].first, placed[th].second);
}
}
if (!found) {
newRows.push_back(i);
}
}
}
for (int i: newRows) {
rowRooks.push_back(i);
placed[i] = make_pair(rowRooks.size(), placed[th].second);
}
columns_placed++;
} else {
int th = rowRooks[rows_placed];
vector < int > newRows;
for (int i = 0; i < n; i++) {
if (placed[i].first == -1 && graph[i][th] == '1') {
bool found = false;
for (int j: columnRooks) {
if (graph[j][i] == '1') {
found = true;
placed[i] = make_pair(placed[th].first, placed[j].second);
}
}
if (!found) {
newRows.push_back(i);
}
}
}
for (int i: newRows) {
columnRooks.push_back(i);
placed[i] = make_pair(placed[th].first, columnRooks.size());
}
rows_placed++;
}
}
// Check if the configuration we reached is a valid configuration
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// If one of the rooks is unplaced, then can't be on the same line or column
if ((placed[i].first == -1) ^ (placed[j].first == -1)) {
if (graph[i][j] == '1') {
ok = false;
return 0;
}
}
// If both rooks are placed, they have to be on different locations
// And they must be on the same row or column iff graph[i][j] is '1'
if ((placed[i].first != -1) && (placed[j].first != -1)) {
if (placed[i] == placed[j]) {
ok = false;
return 0;
}
if (intersect(placed[i], placed[j]) != graph[i][j]) {
ok = false;
return 0;
}
}
}
}
// Remove placed rooks from graph and record new graph
vector < string > remGraph;
for (int i = 0; i < n; i++) {
if (placed[i].first == -1) {
string s = "";
for (int j = 0; j < n; j++) {
if (placed[j].first == -1) s += graph[i][j];
}
remGraph.push_back(s);
}
}
remGraphs[num_rooks] = remGraph;
colSizes[num_rooks] = columnRooks.sz;
rowSizes[num_rooks] = rowRooks.sz;
calc[num_rooks] = 1;
}
// Try placing group 1 rooks on column (th1) or row (th2)
int & ret = pd[num_rooks][Ncol][Nrow];
if (ret == -1) {
int colSize = colSizes[num_rooks];
int rowSize = rowSizes[num_rooks];
long long th1 = 0, th2 = 0;
th1 = (C[Ncol][colSize + 1] * 1 ll * C[Nrow][rowSize + 1]) % mod;
th1 = (th1 * fac[colSize + 1]) % mod;
th1 = (th1 * fac[rowSize + 1]) % mod;
th1 = (th1 * solve(Ncol - 1 - colSize, Nrow - 1 - rowSize, remGraphs[num_rooks])) % mod;
if (colSize != 0) {
th2 = (C[Nrow][colSize + 1] * 1 ll * C[Ncol][rowSize + 1]) % mod;
th2 = (th2 * fac[colSize + 1]) % mod;
th2 = (th2 * fac[rowSize + 1]) % mod;
th2 = (th2 * solve(Ncol - 1 - rowSize, Nrow - 1 - colSize, remGraphs[num_rooks])) % mod;
}
ret = (th1 + th2) % mod;
}
return ret;
}
int RookGraph::countPlacements(int N, vector < string > graph) {
for (int i = 0; i <= 50; i++) {
if (i == 0) fac[i] = 1;
else fac[i] = (fac[i - 1] * i) % mod;
C[i][0] = 1;
for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
memset(pd, -1, sizeof(pd));
int val = solve(N, N, graph);
if (ok == false) return 0;
return val;
}