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;
}