## Tuesday, November 18, 2014

### Codeforces Round #277.5 Div. 2 Problem F

For complete discussion of this round : link to discussion

Problem Statement:
F. Special Matrices

Solution:
An interesting combinatorics DP problem. To solve this problem we need to find a way to reduce the number of parameters that matters. In the end, we only need 2 parameters, which is the current column that is being filled, and the number of rows which has all 0s in it, so we will have an $$O(N^2)$$ solution.

Firstly we need to get the information of how many $$1$$s have to be filled in each column. Store this information in an array to_fill[i]. Furthermore, let D[R][k] be the number of ways to fill all columns in [0..k] where we initially have $$R$$ empty rows). Define cur as the index of current column being considered. We keep a variable $$T$$ initialized to 0, which keeps track of the number of 1s that we have filled as we progress from the first column to the current column (that is, the $$T$$ = sum of to_fill[i] from i = 0 to index of cur). Suppose what at column cur, we have R empty rows and $$S$$ rows that already has one '1' in each of them, and from [0..k] we need to fill $$T$$ number of 1s. Then we have the following relationship:
$$T = 2*R + S$$.

Now, depending on to_fill[cur], we have the following cases:
Case 1: to_fill[cur] = 0
Then we know that D[R][cur] = D[R][cur-1] for all R.

Case 2: to_fill[cur] = 1
Then we have two ways of filling in '1' in this column. We can either choose any of the $$R$$ rows, or any of the $$S$$ rows. Hence D[R][cur] = R*D[R-1][cur-1] (if R > 0) + S*D[R][cur-1] (if S>0).

Case 3: to_fill[cur] = 2
Then we have three ways to fill in two '1's in this column. We either choose two of $$R$$ rows, one of $$R$$ and one of $$S$$, or two of $$S$$. Then we update D[R][cur] accordingly similar to case 1.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int MOD;
int N, M;

long long dp[503][2];
int a[503];

int main(){
int u;
scanf("%d %d", &N, &M);
cin >> MOD;
for(int i=0;i<M;++i){
for(int j=0;j<N;++j){
scanf("%1d", &u);
a[j] += u;
}
}
row[2] = N-M;
for(int i=0;i<=N;++i){
for(int k=0;k<2;++k){
dp[i][k] = 0;
}
}
dp[0][1] = 1;
int tot = 0;
for(int i=0;i<N;++i){
int cross = 2-a[i];
tot += cross;
int cur = (i & 1);
int prev = (i & 1) ^ 1;
if(cross == 0) {
for(int j=0;j<=N;++j){
dp[j][cur] = dp[j][prev];
}
} else if (cross == 1) {
for(int j=0;j<=N;++j){
int k = tot - 2*j;
dp[j][cur] = 0;
if(j>0){
dp[j][cur] += 1LL * j * dp[j-1][prev];
dp[j][cur] %= MOD;
}
if(k>0){
dp[j][cur] += 1LL * k * dp[j][prev];
dp[j][cur] %= MOD;
}
}
} else if (cross == 2) {
for(int j=0;j<=N;++j){
int k = tot - 2*j;
dp[j][cur] = 0;
if(j>1) {
dp[j][cur] += 1LL * j * (j-1) / 2 * dp[j-2][prev];
dp[j][cur] %= MOD;
}
if(k>1) {
dp[j][cur] += 1LL * k * (k-1) / 2 * dp[j][prev];
dp[j][cur] %= MOD;
}
if(j>0 && k>0) {
dp[j][cur] += 1LL * j * k * dp[j-1][prev];
dp[j][cur] %= MOD;
}
}
}

}
cout << dp[row[2]][(N-1)&1] << endl;
return 0;
}