题目详情提交记录（0）

宋亦然家今天的饭 题解

userId_undefined

复仇者_帅童

CSP-J一等奖出题人

2025-08-14 22:10:04

发布于：浙江

59阅读
0回复
0点赞

今天模拟赛的题目，赛时 84pts。

题意解析：宋亦然会做很多菜，她掌握了 nn 种烹饪方法，她还有 mm 种主要食材。求符合以下要求的方案数：

  • 做的菜的数量大于等于 11。
  • 做的每道菜烹饪方法均不相同。
  • 记做的菜的数量为 tt，则同一种主要食材不能使用超过 ⌊t2⌋\lfloor\frac{t}{2}\rfloor 次。

64pts

由于需要烹饪方法不同，所以考虑枚举烹饪方法，对菜进行选择。

我们用 dp[i][j][k][l]dp[i][j][k][l] 记录前 ii 个烹饪方法，出现了 jj 个主要食材 11，kk 个主要食材 22，ll 个主要食材 33 的方案数。
转移方程挺好写的，枚举烹饪方法后再枚举食材即可。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
int a[105][2005];
int dp[45][45][45][45];
int n, m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	if(m <= 3){
		dp[0][0][0][0] = 1;
		for(int i = 1; i <= n; i++){
			for(int j = 0; j <= i; j++){
				for(int k = 0; k <= i - j; k++){
					for(int l = 0; l <= i - j - k; l++){
						dp[i][j][k][l] = dp[i - 1][j][k][l];
						if(j) dp[i][j][k][l] += dp[i - 1][j - 1][k][l] * a[i][1];
						if(k) dp[i][j][k][l] += dp[i - 1][j][k - 1][l] * a[i][2];
						if(l) dp[i][j][k][l] += dp[i - 1][j][k][l - 1] * a[i][3];
						dp[i][j][k][l] %= mod;
					}
				}
			}
		}
		int ans = 0;
		for(int j = 0; j <= n; j++){
			for(int k = 0; k <= n - j; k++){
				for(int l = 0; l <= n - j - k; l++){
					int siz = j + k + l;
					if(j <= siz / 2 && k <= siz / 2 && l <= siz / 2) ans = (ans + dp[n][j][k][l]) % mod;
				}
			}
		}
		cout << ans - 1;
	}else{
		cout << "I don't know how to do it!!!";
	}
	
	return 0;
}

时间复杂度 O(nm+1)O(n^{m+1})，空间复杂度 O(nm+1)O(n^{m+1})。

84pts

按照上面的方法没什么前途了，不妨正难则反，先求出不考虑条件三的总情况数，再求出违反条件三的情况即可。

注意到如果违反条件三，则使用最多的食材的使用次数一定大于其他食材的使用次数。所以我们考虑按照这种方法 DP：

dp[i][j][k][l]dp[i][j][k][l] 表示前 ii 个烹饪方法，第 jj 种食材使用了 kk 次，其他食材使用了 ll 次的方案数。状态转移方程如下：

dp[i][j][k][l]=dp[i−1][j][k−1][l]×Ai,j+dp[i−1][j][k][l−1]×((∑p=1mAi,p)−Ai,j)dp[i][j][k][l]=dp[i-1][j][k-1][l]\times A_{i,j}+dp[i-1][j][k][l-1]\times ((\sum_{p=1}^{m} A_{i,p})-A_{i,j})

预处理出所有的 (∑p=1mAi,p)−Ai,j(\sum_{p=1}^{m} A_{i,p})-A_{i,j} 即可。

当然，这样 DP 空间可能过大，所以应使用滚动数组减少一个维度。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
int a[105][2005];
int other[105][2005];
int dp[501][41][41], tmp[501][41][41];
int n, m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int all = 1;
	for(int i = 1; i <= n; i++){
		int sum = 0;
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			sum += a[i][j];
		}
		for(int j = 1; j <= m; j++){
			other[i][j] = sum - a[i][j];
		}
		all = all * (sum + 1) % mod;
	}
	for(int i = 1; i <= m; i++) dp[i][0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			for(int k = 0; k <= n; k++){
				for(int l = 0; l <= n; l++){
					tmp[j][k][l] = dp[j][k][l];
				}
			}
		}
		for(int j = 1; j <= m; j++){
			for(int k = 0; k <= n; k++){
				for(int l = 0; l <= n; l++){
					if(k) dp[j][k][l] += tmp[j][k - 1][l] * a[i][j];
					if(l) dp[j][k][l] += tmp[j][k][l - 1] * other[i][j];
					dp[j][k][l] %= mod;
				}
			}
		}
		
	}
	int ans = 0;
	for(int i = 0; i <= m; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 0; k < j; k++){
				ans = (ans + dp[i][j][k]) % mod;
			}
		}
	}
	cout << (all - ans - 1 + mod) % mod;
	
	return 0;
}

时间复杂度 O(n3m)O(n^3m)，空间复杂度 O(n2m)O(n^2m)。

100pts

模拟赛时时间不够没写出来。

注意到，我们只需要求所有 k>lk\gt l 的状态数，不妨直接用 k−lk-l 代替 k,lk,l 两个数，此时我们只需要判断第三维是否大于 00 即可。

状态转移方程也就变成了：

dp[i][j][k]=dp[i−1][j][k−1]×Ai,j+dp[i−1][j][k+1]×((∑p=1mAi,p)−Ai,j)dp[i][j][k]=dp[i-1][j][k-1]\times A_{i,j}+dp[i-1][j][k+1]\times ((\sum_{p=1}^{m} A_{i,p})-A_{i,j})

在实现的过程中，需要注意以下几点：

  • k−lk-l 可能会小于 00，所以应该加上偏移量 nn。
  • 依然要开滚动数组。
  • 记得对 ∑Ai,j\sum A_{i,j} 取模，不然会爆 long long！
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
int a[105][2005];
int other[105][2005];
int dp[2001][201], tmp[2001][201];
int n, m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int all = 1;
	for(int i = 1; i <= n; i++){
		int sum = 0;
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			sum += a[i][j];
		}
		sum %= mod;
		for(int j = 1; j <= m; j++){
			other[i][j] = (sum - a[i][j] + mod) % mod;
		}
		all = all * (sum + 1) % mod;
	}
	for(int i = 1; i <= m; i++) dp[i][n] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			for(int k = 0; k <= n * 2; k++){
				tmp[j][k] = dp[j][k];
			}
		}
		for(int j = 1; j <= m; j++){
			for(int k = 0; k <= n * 2; k++){
				if(k) dp[j][k] += tmp[j][k - 1] * a[i][j];
				dp[j][k] += tmp[j][k + 1] * other[i][j];
				dp[j][k] %= mod;
			}
		}
		
	}
	int ans = 0;
	for(int i = 1; i <= m; i++){
		for(int j = n + 1; j <= n * 2; j++){
			ans = (ans + dp[i][j]) % mod;
		}
	}
	cout << (all - ans - 1 + mod) % mod;
	
	return 0;
}

时间复杂度 O(n2m)O(n^2m)，空间复杂度 O(nm)O(nm)。

Markdown:

今天模拟赛的题目，赛时 84pts。

---
题意解析：宋亦然会做很多菜，她掌握了 $n$ 种烹饪方法，她还有 $m$ 种主要食材。求符合以下要求的方案数：

- 做的菜的数量大于等于 $1$。
- 做的每道菜烹饪方法均不相同。
- 记做的菜的数量为 $t$，则同一种主要食材不能使用超过 $\lfloor\frac{t}{2}\rfloor$ 次。

## 64pts
由于需要烹饪方法不同，所以考虑枚举烹饪方法，对菜进行选择。

我们用 $dp[i][j][k][l]$ 记录前 $i$ 个烹饪方法，出现了 $j$ 个主要食材 $1$，$k$ 个主要食材 $2$，$l$ 个主要食材 $3$ 的方案数。
转移方程挺好写的，枚举烹饪方法后再枚举食材即可。

\`\`\`cpp
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
int a[105][2005];
int dp[45][45][45][45];
int n, m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	if(m <= 3){
		dp[0][0][0][0] = 1;
		for(int i = 1; i <= n; i++){
			for(int j = 0; j <= i; j++){
				for(int k = 0; k <= i - j; k++){
					for(int l = 0; l <= i - j - k; l++){
						dp[i][j][k][l] = dp[i - 1][j][k][l];
						if(j) dp[i][j][k][l] += dp[i - 1][j - 1][k][l] * a[i][1];
						if(k) dp[i][j][k][l] += dp[i - 1][j][k - 1][l] * a[i][2];
						if(l) dp[i][j][k][l] += dp[i - 1][j][k][l - 1] * a[i][3];
						dp[i][j][k][l] %= mod;
					}
				}
			}
		}
		int ans = 0;
		for(int j = 0; j <= n; j++){
			for(int k = 0; k <= n - j; k++){
				for(int l = 0; l <= n - j - k; l++){
					int siz = j + k + l;
					if(j <= siz / 2 && k <= siz / 2 && l <= siz / 2) ans = (ans + dp[n][j][k][l]) % mod;
				}
			}
		}
		cout << ans - 1;
	}else{
		cout << "I don't know how to do it!!!";
	}
	
	return 0;
}
\`\`\`

时间复杂度 $O(n^{m+1})$，空间复杂度 $O(n^{m+1})$。

## 84pts

按照上面的方法没什么前途了，不妨正难则反，先求出不考虑条件三的总情况数，再求出违反条件三的情况即可。

注意到如果违反条件三，则**使用最多的食材的使用次数一定大于其他食材的使用次数**。所以我们考虑按照这种方法 DP：

$dp[i][j][k][l]$ 表示前 $i$ 个烹饪方法，第 $j$ 种食材使用了 $k$ 次，其他食材使用了 $l$ 次的方案数。状态转移方程如下：

$$
dp[i][j][k][l]=dp[i-1][j][k-1][l]\times A_{i,j}+dp[i-1][j][k][l-1]\times ((\sum_{p=1}^{m} A_{i,p})-A_{i,j})
$$

预处理出所有的 $(\sum_{p=1}^{m} A_{i,p})-A_{i,j}$ 即可。

当然，这样 DP 空间可能过大，所以应使用滚动数组减少一个维度。

\`\`\`cpp
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
int a[105][2005];
int other[105][2005];
int dp[501][41][41], tmp[501][41][41];
int n, m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int all = 1;
	for(int i = 1; i <= n; i++){
		int sum = 0;
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			sum += a[i][j];
		}
		for(int j = 1; j <= m; j++){
			other[i][j] = sum - a[i][j];
		}
		all = all * (sum + 1) % mod;
	}
	for(int i = 1; i <= m; i++) dp[i][0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			for(int k = 0; k <= n; k++){
				for(int l = 0; l <= n; l++){
					tmp[j][k][l] = dp[j][k][l];
				}
			}
		}
		for(int j = 1; j <= m; j++){
			for(int k = 0; k <= n; k++){
				for(int l = 0; l <= n; l++){
					if(k) dp[j][k][l] += tmp[j][k - 1][l] * a[i][j];
					if(l) dp[j][k][l] += tmp[j][k][l - 1] * other[i][j];
					dp[j][k][l] %= mod;
				}
			}
		}
		
	}
	int ans = 0;
	for(int i = 0; i <= m; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 0; k < j; k++){
				ans = (ans + dp[i][j][k]) % mod;
			}
		}
	}
	cout << (all - ans - 1 + mod) % mod;
	
	return 0;
}
\`\`\`

时间复杂度 $O(n^3m)$，空间复杂度 $O(n^2m)$。

## 100pts

模拟赛时时间不够没写出来。

注意到，我们只需要求所有 $k\gt l$ 的状态数，不妨直接用 $k-l$ 代替 $k,l$ 两个数，此时我们只需要判断第三维是否大于 $0$ 即可。

状态转移方程也就变成了：
$$
dp[i][j][k]=dp[i-1][j][k-1]\times A_{i,j}+dp[i-1][j][k+1]\times ((\sum_{p=1}^{m} A_{i,p})-A_{i,j})
$$

在实现的过程中，需要注意以下几点：
- $k-l$ 可能会小于 $0$，所以应该加上偏移量 $n$。
- 依然要开滚动数组。
- 记得对 $\sum A_{i,j}$ 取模，不然会爆 `long long`！

\`\`\`cpp
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
int a[105][2005];
int other[105][2005];
int dp[2001][201], tmp[2001][201];
int n, m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int all = 1;
	for(int i = 1; i <= n; i++){
		int sum = 0;
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			sum += a[i][j];
		}
		sum %= mod;
		for(int j = 1; j <= m; j++){
			other[i][j] = (sum - a[i][j] + mod) % mod;
		}
		all = all * (sum + 1) % mod;
	}
	for(int i = 1; i <= m; i++) dp[i][n] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			for(int k = 0; k <= n * 2; k++){
				tmp[j][k] = dp[j][k];
			}
		}
		for(int j = 1; j <= m; j++){
			for(int k = 0; k <= n * 2; k++){
				if(k) dp[j][k] += tmp[j][k - 1] * a[i][j];
				dp[j][k] += tmp[j][k + 1] * other[i][j];
				dp[j][k] %= mod;
			}
		}
		
	}
	int ans = 0;
	for(int i = 1; i <= m; i++){
		for(int j = n + 1; j <= n * 2; j++){
			ans = (ans + dp[i][j]) % mod;
		}
	}
	cout << (all - ans - 1 + mod) % mod;
	
	return 0;
}
\`\`\`
时间复杂度 $O(n^2m)$，空间复杂度 $O(nm)$。
userId_undefined
去预览
0/2000

全部评论 2

暂无数据

提交答案之后，这里将显示提交结果～

首页