题面

求出满足以下条件的 n*m 的 01 矩阵个数：

（1）第 i 行第 1~li 列恰好有 1 个 1。

（2）第 i 行第 ri~m 列恰好有 1 个 1。

（3）每列至多有 1 个 1。

n,m<=3000

题解

CODE

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3005;

const int mod = 998244353;

int n, m, f[MAXN][MAXN], sl[MAXN], sr[MAXN];

int main () {

	scanf("%d%d", &n, &m);

	for(int i = 1, l, r; i <= n; ++i) scanf("%d%d", &l, &r), ++sl[l], ++sr[r];

	for(int i = 1; i <= m; ++i) sl[i] += sl[i-1], sr[i] += sr[i-1];

	f[0][0] = 1;

	for(int i = 1; i <= m; ++i) {

		f[i][0] = f[i-1][0];

		for(int j = 1; j <= i; ++j)

			f[i][j] = (f[i-1][j] + 1ll * f[i-1][j-1] * (sr[i]-(j-1))) % mod;

		for(int j = sl[i-1]; j < sl[i]; ++j)

			for(int k = 0; k <= i; ++k)

				f[i][k] = 1ll * f[i][k] * (i-j - k) % mod;

	}

	printf("%d\n", f[m][n]);

}

巴特西

CSP模拟赛 Matrix（DP）

题面

题解

CODE

最新文章

热门文章