CodeForces 489F DP Special Matrices

首先统计一下前m行中，有x列1的个数为0，有y列1的个数为1.

设d(i, j)表示有i列1的个数为0，有j列1的个数为1，能到达这个状态的矩阵的个数。

则d(x, y) = 1

每一行都是两个1一起放，枚举这两个1分别放在了哪种列上面

于是有状态转移：

• d(i - 2, j + 2) += d(i, j) * C(i, 2)
• d(i - 1, j) += d(i, j) * i * j
• d(i, j - 2) += d(i, j) * C(j, 2)

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

const int maxn = 500 + 10;

int n, m;

long long d[maxn][maxn], MOD;

char s[maxn];
int cnt[maxn];

int main()
{
    scanf("%d%d%I64d", &n, &m, &MOD);
    for(int i = 0; i < m; i++)
    {
        scanf("%s", s);
        for(int j = 0; j < n; j++) if(s[j] == '1') cnt[j]++;
    }

    int zero = 0, ones = 0;
    for(int i = 0; i < n; i++) if(!cnt[i]) zero++; else if(cnt[i] == 1) ones++;

    d[zero][ones] = 1;
    for(int i = n; i >= 0; i--)
        for(int j = n; j >= 0; j--)
        {
            if(i >= 2) d[i-2][j+2] = (d[i-2][j+2] + d[i][j] * i * (i - 1) / 2) % MOD;
            if(i && j) d[i-1][j] = (d[i-1][j] + d[i][j] * i * j) % MOD;
            if(j >= 2) d[i][j-2] = (d[i][j-2] + d[i][j] * j * (j - 1) / 2) % MOD;
        }

    printf("%I64d
", d[0][0]);

    return 0;
}