1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; const int MOD = 998244353; const int MAXN = 100; // 烹饪方法 const int MAXM = 2000; // 食材 int n, m; int a[MAXN + 5][MAXM + 5]; int sum[MAXN + 5]; // sum[i] = sum(a[i][1]~a[i][m]) // O(mn^3) = 84pt namespace subtask1 { // 第wa种食材用多了时 // 前i种烹饪方法中,有j种用了wa食材,k种用了其他食材,的方案数 int f[MAXN + 5][MAXN + 5][MAXN + 5]; // 前 i 种烹饪方式,炒出 j 道菜一共多少种方案 int g[MAXN + 5][MAXN + 5]; // 总方案,失败方案 int all, sub; void work() { all = sub = 0; // 预处理 g[][] // 考虑有没有使用第 i 种烹饪方式 g[0][0] = 1; for (int i = 1; i <= n; i++) { g[i][0] = 1; for (int j = 1; j <= n; j++) g[i][j] = (g[i - 1][j] + sum[i] * g[i - 1][j - 1] % MOD) % MOD; } for (int i = 1; i <= n; i++) all = (all + g[n][i]) % MOD; // 枚举每种 j 对应的食材 for (int wa = 1; wa <= m; wa++) { memset(f, 0, sizeof(f)); // 处理 f[][][] f[0][0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= i; j++) { for (int k = 0; j + k <= i; k++) { // f[i - 1][j][k]:不用第 i 种烹饪方式 // a[i][wa] * f[i - 1][j - 1][k]:第 i 种烹饪方式烹饪了 wa 食材 //(sum[i] - a[i][wa]) * f[i - 1][j][k - 1]:第 i 种烹饪方式烹饪了其他食材 f[i][j][k] = f[i - 1][j][k]; if (j > 0) f[i][j][k] += a[i][wa] * f[i - 1][j - 1][k] % MOD; if (k > 0) f[i][j][k] += (sum[i] - a[i][wa] + MOD) % MOD * f[i - 1][j][k - 1] % MOD; f[i][j][k] %= MOD; // 计数 gg if (i == n && j > k) sub = (sub + f[i][j][k]) % MOD; } } } } cout << (all - sub + MOD) % MOD << "\n"; } } // O(mn^2) 100pt namespace subtask2 { // 第wa种食材用多了时 // 前i种烹饪方法中,wa食材比其他食材多用了 j 个,的方案数 int f[MAXN + 5][2 * MAXN + 5]; int BASE = MAXN; // 前 i 种烹饪方式,炒出 j 道菜一共多少种方案 int g[MAXN + 5][MAXN + 5]; // 总方案,失败方案 int all, sub; void work() { all = sub = 0; // 预处理 g[][] // 考虑有没有使用第 i 种烹饪方式 g[0][0] = 1; for (int i = 1; i <= n; i++) { g[i][0] = 1; for (int j = 1; j <= n; j++) g[i][j] = (g[i - 1][j] + sum[i] * g[i - 1][j - 1] % MOD) % MOD; } for (int i = 1; i <= n; i++) all = (all + g[n][i]) % MOD; // 枚举每种 j 对应的食材 for (int wa = 1; wa <= m; wa++) { memset(f, 0, sizeof(f)); // 处理 f[][][] f[0][0 + BASE] = 1; for (int i = 1; i <= n; i++) { for (int j = -i; j <= i; j++) { f[i][j + BASE] = f[i - 1][j + BASE]; f[i][j + BASE] += a[i][wa] * f[i - 1][j - 1 + BASE] % MOD; f[i][j + BASE] += (sum[i] - a[i][wa] + MOD) % MOD * f[i - 1][j + 1 + BASE] % MOD; f[i][j + BASE] %= MOD; if (i == n && j > 0) sub = (sub + f[i][j + BASE]) % MOD; } } } cout << (all - sub + MOD) % MOD << "\n"; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cin >> a[i][j]; sum[i] = (sum[i] + a[i][j]) % MOD; } if (n <= 40 && m <= 500) subtask1::work(); else subtask2::work(); return 0; }
- 1
信息
- ID
- 43
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 10
- 已通过
- 5
- 上传者