489F - Special Matrices - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const int N = 510;
const int INF = INT_MAX;
const string NAME = "solve";

int n,m;
int cnt_1,cnt_0;
int dp[N][N],mod;
int col[N];
int id;

void add(int &x, const int y) {
    x += y;
    if(x >= mod) {
        x -= mod;
    }
}

int calc(int x) {
    return 1LL*x*(x-1)/2%mod;
}

signed main()
{
    if (fopen((NAME + ".inp").c_str(), "r")) {
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> mod;
    for(int i = 1 ; i <= m ; i++) {
        string s; cin >> s;
        for(int j = 1 ; j <= n ; j++) {
            if(s[j-1] == '1') {
                col[j]++;
            }
        }
    }
    for(int i = 1 ; i <= n ; i++) {
        if(col[i] > 2) {
            cout << 0;
            return 0;
        }
        if(col[i] == 0) {
            cnt_0++;
        }
        if(col[i] == 1) {
            cnt_1++;
        }
    }
    dp[0][0] = 1;
    for(int dem_0 = 0 ; dem_0 <= n ; dem_0++) {
        for(int dem_1 = 0 ; dem_1+dem_0 <= n ; dem_1++) {
            if(dem_0 > 1) {
                /// chon 2 o 0
                add(dp[dem_0][dem_1],1LL*dp[dem_0-2][dem_1+2]*calc(dem_0)%mod);
            }
            if(dem_1 > 1) {
                /// chon 2 o 1
                add(dp[dem_0][dem_1],1LL*dp[dem_0][dem_1-2]*calc(dem_1)%mod);
            }
            if(dem_0 > 0) {
                /// chon 1 o 1 va 1 o 0
                add(dp[dem_0][dem_1],1LL*dp[dem_0-1][dem_1]*dem_0%mod*dem_1%mod);
            }
        }
    }
    cout << dp[cnt_0][cnt_1];
    return 0;
}