#3211. 「CSP-S 2019」Emiya 家今天的饭
Summarize
在 $n\times m$ 的矩阵中选 $k$ 个元素，要求 $k\ge 1$，每行最多选 $1$ 个元素，每列元素个数不超过 $\lfloor \frac{k}{2}\rfloor$ 的方案数。
$n\le 100,m\le 2000$
Solution
84 pts
注意到如果某一列不符合条件 3，则其他列必然都符合。
可以先不考虑条件 3，用背包动态规划计算出所有可行方案数。然后枚举不符合条件的列，设其编号为 $c$；记 $f[i][j][k]$ 为在前 $i$ 行中选出 $j$ 个物品，且第 $c$ 列恰好选了 $k$ 个的方案数。
时间复杂度 $O(n^3m)$，可以得到 84 分。
100 pts
优化第二个动态规划，记 $f[i][j]$ 为在前 $i$ 行中，在第 $c$ 列中选出的物品比其他物品个数多 $j$ 的方案数，即可优化一维。
事件复杂度 $O(n^2m)$，可以得到 100 分。
Note
推性质，不能无脑设计状态然后优化。一定要依赖性质。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const int MAXN = 105;
const int MAXM = 2005;
int n, m;
ll a[MAXN][MAXM], s[MAXN];
ll f[MAXN][MAXN * 2], g[MAXN];
int main() {
freopen("meal.in", "r", stdin);
freopen("meal.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) scanf("%lld", &a[i][j]), s[i] = (s[i] + a[i][j]) % MOD;
g[0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = i; j >= 1; --j) g[j] = (g[j] + g[j - 1] * s[i] % MOD) % MOD;
ll ans = 0;
for (int i = 1; i <= n; ++i) ans = (ans + g[i]) % MOD;
for (int c = 1; c <= m; ++c) {
memset(f, 0, sizeof(f));
f[0][n] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= 2 * n; ++j) {
if (j == 0)
f[i][j] = (f[i - 1][j] + f[i - 1][j + 1] * (s[i] - a[i][c] + MOD) % MOD) % MOD;
else
f[i][j] = (f[i - 1][j] + f[i - 1][j + 1] * (s[i] - a[i][c] + MOD) % MOD +
f[i - 1][j - 1] * a[i][c] % MOD) %
MOD;
}
}
for (int i = 1; i <= n; ++i) ans = (ans - f[n][n + i] + MOD) % MOD;
}
cout << ans << endl;
return 0;
}
|