PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Utkarsh Gupta
Tester: Tejas Pandey
Editorialist: Nishank Suresh
DIFFICULTY:
2319
PREREQUISITES:
Combinatorics
PROBLEM:
You have an N\times M grid, each cell of which can be colored either red or green. The score of a colored grid is the number of right-down paths from (1, 1) to (N, M) such that the number of red cells equals the number of green cells on this path.
Find the sum of scores across possible colorings of the grid.
EXPLANATION:
This task can be solved with a trick that’s rather common in counting problems, sometimes called the contribution trick.
Whenever you need to fix a configuration and count the number of objects in it that satisfy some property, you can often instead fix an object that satisfies that property and count how many configurations it appears in — the sum of both values is the same.
Let’s do the same thing here. We want to
- Fix a coloring of the grid
- Look at a right-down path from (1, 1) to (N, M)
- Count it if it has an equal number of red and green cells
Instead, we will
- Fix a right-down path from (1, 1) to (N, M)
- Color it in such a way that the number of red and green cells is equal
- Then, count the number of grids that contain this path
Summing this across all paths is the the final answer.
Now, let’s see how to compute this.
- First, we need to fix a path. There are \binom{N+M-2}{M-1} paths from (1, 1) to (N, M) — this is a well-known result.
- An easy proof is that you make exactly N+M-2 steps in total with M-1 of them being right and N-1 being down, so fixing the positions of the right steps fixes the path.
- Next, we need to color the path correctly.
- Let the length of the path be $L. Note that L = N + M - 1.
- If L is odd, there is no way to color the path correctly
- Otherwise, we simply fix the positions of the green cells in \binom{L}{L/2} ways, which then also fixes the red cells
- Finally, we want to know how many grids this path appears in. We’ve fixed the colors of cells on the path, but everything else is completely free and has two choices each (red or green).
- This gives us 2^{N\cdot M - L} grids that contain this path.
So, the final answer is simply
where L = N + M - 1. Note that the answer is 0 when L is odd.
The binomial coefficients can be precomputed in a 2000\times 2000 table using Pascal’s identity since we only need something like \binom{2000}{1000} at worst. Similarly, the powers of 2 upto 10^6 can be precomputed.
This allows each query to be answered in \mathcal{O}(1) time.
There are of course other ways to compute binomial coefficients (for example, the standard factorial + inverse factorial method) and powers of 2 (via binary exponentiation), if you want to do something else.
TIME COMPLEXITY
\mathcal{O}(1) or \mathcal{O}(\log {MOD}) per test case, depending on implementation.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define maxn 10007
#define mod 998244353
long long int fact[maxn], ifact[maxn];
long long int mpow(long long int a, long long int b) {
long long int res = 1;
while(b) {
if(b&1) res *= a, res %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return res;
}
void pre() {
fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
for(int i = 2; i < maxn; i++) fact[i] = fact[i - 1]*i, fact[i] %= mod;
for(int i = 2; i < maxn; i++) ifact[i] = ifact[i - 1]*mpow(i, mod - 2), ifact[i] %= mod;
}
long long int comb(long long int a, long long int b) {
if(b == 0) return 1LL;
long long int ans = fact[a];
ans *= ifact[b];
ans %= mod;
ans *= ifact[a - b];
ans %= mod;
return ans;
}
int main() {
pre();
int t;
cin >> t;
while(t--) {
int n, m;
cin >> n >> m;
if((n + m - 1)&1) cout << "0\n";
else {
long long int paths = comb(n + m - 2, m - 1);
paths *= ((fact[n + m - 1]*((ifact[(n + m - 1)/2]*ifact[(n + m - 1)/2])%mod))%mod);
paths %= mod;
paths *= mpow(2, n*m - (n + m - 1));
paths %= mod;
cout << paths << "\n";
}
}
return 0;
}
Editorialist's code (Python)
mod = 998244353
N = 2005
C = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
C[i][0] = 1
for i in range(1, N):
for j in range(1, i+1):
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod
for _ in range(int(input())):
n, m = map(int, input().split())
len = n + m - 1
ans = C[n+m-2][m-1] * C[len][len//2] * pow(2, n*m - len, mod)
if len%2 == 1:
ans = 0
print(ans%mod)
