Emiya家的饭-题目解析（详细）

2025-08-15 11:26:05

发布于：浙江

24阅读

0回复

0点赞

链接描述
这道题有点非人。
可以一点一点的做出来。
1.32 $pts$ 做法-暴力搜索：
注意到前八个测试点 $n\le10$ ， $m\le3$ 。
是可以使用DFS的数据范围。
顺便提一下题意：她会做 $a_{i,j}$ 道不同的使用方法 $i$ 和主要食材 $j$ 的菜。
然后就是思考如何使用DFS了。
因为Rin的要求是每道菜的烹饪方式互不相同，所以在DFS的过程中可以将参数 $x$ 设为使用的烹饪方式。
然后对于每种烹饪方式，选择一种主要食材，然后在最后进行一些操作。
错误的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod=998244353;
int n,m;
int a[55][55];
int vis[55];
int co[55];
ll ans=0;
void check(){
	memset(co,0,sizeof co);
	int num=0;
	int mm=0;
	for(int i=1;i<=n;i++){
		if(!vis[i])continue;
		num++;
		co[vis[i]]++;
		mm=max(mm,co[vis[i]]);
	}
	if(num==0||mm>(num/2))return;
	ll sum=1;
	for(int i=1;i<=n;i++){
		sum+=a[i][vis[i]];
		sum%=mod;
	}
	ans+=sum;
	return;
}
void dfs(int x){
	if(x==n+1){
		check();
		return;
	}
	for(int i=0;i<=m;i++){
		vis[x]=i;
		dfs(x+1);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dfs(1);
	cout<<ans;
	return 0;
}

正确的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long mod=998244353;
int n,m;
int a[5005][5050];
int vis[5005];
int co[5005];
ll ans=0;
void check(){
	memset(co,0,sizeof co);
	int num=0;
	int mm=0;
	for(int i=1;i<=n;i++){
		if(!vis[i])continue;
		num++;
		co[vis[i]]++;
		mm=max(mm,co[vis[i]]);
	}
	if(num==0||mm>(num/2))return;
	ll sum=1;
	for(int i=1;i<=n;i++){
		if(vis[i]==0)continue; 
		sum=sum*a[i][vis[i]]%mod;
	}
	ans+=sum;
    ans%=mod;
	return;
}
void dfs(int x){
	if(x==n+1){
		check();
		return;
	}
	for(int i=0;i<=m;i++){
		vis[x]=i;
		dfs(x+1);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dfs(1);
	cout<<ans;
	return 0;
}

正确的对比错误的，主要改了这几个点：
首先在 $check()$ 函数的第二个 $for$ 循环中，当 $vis[i]$ 等于零时，是需要先跳过的，不然之前的全都会清零。
其次， $sum$ 的取余应该放在里面。 $ans$ 也应该取余。
接着第二个 $for$ 循环当中的 $sum$ 的计算应该是乘法而不是加法。
因为有 $a_{i,j}$ 种使用 $i$ 烹饪方式和 $j$ 个主要食材的菜。
所以最终方案数应该是乘在一起产生xxx种排饭方式，具体可以参考排列组合。
然后就是 $64pts$ 的暴力DP。
是这样的：可以建立一个四维DP数组： $dp[45][45][45][45]$ 。
通过某些观察发现前十六个点都拥有 $m\le3$ 的测试数据。
也就是说，只有3种主要食材。
$dp[i][x][y][z]$ 表示使用了前 $i$ 种烹饪方式，做了 $x$ 道使用了第一种主要食材的菜，做了 $y$ 道使用了第二种主要食材的菜，做了 $z$ 道使用了第三种主要食材的菜的方案数。
思考一下状态转移方程：
第一种：不做任何菜 $f[i][x][y][z]+=f[i-1][x][y][z]$
第二种：做第一种食材的菜 $f[i][x][y][z]+=f[i-1][x-1][y][z]*a[i][1]$
第三种：做第二种食材的菜 $f[i][x][y][z]+=f[i-1][x][y-1][z]*a[i][2]$
第四种：做第三种食材的菜 $f[i][x][y][z]+=f[i-1][x][y][z-1]*a[i][3]$
做完了一个神秘的四层循环后，你会得到一个完善的四维DP数组。
然后要做的就是在这些方案中剔除一些错误的，保留正确的。
判断的话就跟DFS的判断是差不多的。
这是错误代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=998244353;
int n,m;
int a[5005][5005];
int dp[45][45][45][45];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dp[0][0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int x=0;x<=i;x++){
			for(int y=0;y<=i;y++){
				for(int z=0;z<=i;z++){
					dp[i][x][y][z]+=dp[i-1][x][y][z];
					if(x>=1)dp[i][x][y][z]+=dp[i-1][x-1][y][z]*a[i][1]%mod;
					if(y>=1)dp[i][x][y][z]+=dp[i-1][x][y-1][z]*a[i][2]%mod;
					if(z>=1)dp[i][x][y][z]+=dp[i-1][x][y][z-1]*a[i][3]%mod;
                    dp[i][x][y][z]%=mod;
                }
			}
		}
	}
	long long ans=0;
	for(int x=0;x<=n;x++){
		for(int y=0;y<=n;y++){
			for(int z=0;z<=n;z++){
				int mx=max(x,max(y,z));
				int num=x+y+z;
				if(num==0||mx>(num/2))continue;
				ans+=dp[n][x][y][z];
				ans%=mod;
			}
		}
	}
	cout<<ans;
	return 0;
}

这是正确的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=998244353;
int n,m;
int a[5005][5005];
ll dp[45][45][45][45];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dp[0][0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int x=0;x<=i;x++){
			for(int y=0;y<=i;y++){
				for(int z=0;z<=i;z++){
					dp[i][x][y][z]+=dp[i-1][x][y][z];
					if(x>=1)dp[i][x][y][z]+=dp[i-1][x-1][y][z]*a[i][1]%mod;
					if(y>=1)dp[i][x][y][z]+=dp[i-1][x][y-1][z]*a[i][2]%mod;
					if(z>=1)dp[i][x][y][z]+=dp[i-1][x][y][z-1]*a[i][3]%mod;
                    dp[i][x][y][z]%=mod;
                }
			}
		}
	}
	long long ans=0;
	for(int x=0;x<=n;x++){
		for(int y=0;y<=n;y++){
			for(int z=0;z<=n;z++){
				int mx=max(x,max(y,z));
				int num=x+y+z;
				if(num==0||mx>(num/2))continue;
				ans+=dp[n][x][y][z];
				ans%=mod;
			}
		}
	}
	cout<<ans;
	return 0;
}

只有一个错误，就是 $dp$ 数组要开 $longlong$ 。
因为在四维DP和数组A相乘的过程中，可能会爆 $int$ 。
然后就是 $84pts$ 的做法。
注意到（注意力惊人）对于每一种方案，其实我们只关心使用最多的食材和其他食材总数，所以我们可以尝试钦定主要食材。
注意：最多1个食材会超过使用食材的一半。
所以，可以将四维DP简化成这样: $dp[45][405][405]$ 。
$dp[i][x][y]$ 的状态表示是在有 $i$ 种烹饪方式，选中的主要食材 $k$ 有 $x$ 个，其他主要食材的数量为 $y$ 的方案数。
这个状态表示有点怪怪的，因为有一个不表示在下标中的变量： $k$ 。
所以说，你可能需要循环 $n$ 次去进行一个三维的循环，不过还好。
因为在前21个测试点中，有 $n\le40$ 的限制。
所以其实不会超时。
再考虑一下它的状态转移方程：
1.不做新的菜： $dp[i][x][y]+=dp[i-1][x][y]$
2.做 $k$ 号食材的菜： $dp[i][x][y]+=dp[i-1][x-1][y]*a[i][k]$
3.做其他食材的菜： $dp[i][x][y]+=dp[i-1][x][y-1]* (\sum_{j = 1}^{m} a[i][j]-a[i][k])$ 。
注释：
其实这种方法到最后求的不是“满足条件的方案数”而是将所有可能的方案全部算出后，再去求“不满足条件的方案数”
然后就可以开始写一些神秘的代码。

#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;
ll a[45][505];
ll mod=998244353;
ll dp[45][405][405];
ll sum[405];
//tot初始值为1
ll tot=1;
void solve(int tar){
    //初始化
    dp[0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int x=0;x<=i;x++){
			for(int y=0;y<=i;y++){
				dp[i][x][y]=dp[i-1][x][y];
				if(x>=1)dp[i][x][y]=dp[i][x][y]+dp[i-1][x-1][y]*a[i][tar]%mod;
				if(y>=1)dp[i][x][y]=dp[i][x][y]+dp[i-1][x][y-1]*(sum[i]-a[i][tar])%mod;
			    //还需要再加一条：因为(sum[i]-a[i][tar])可能是负数。
                dp[i][x][y]=((dp[i][x][y])%mod+mod)%mod;
            }
		}
	}
	for(int x=0;x<=n;x++){
		for(int y=0;y<x;y++){
			tot=((tot-dp[n][x][y])%mod+mod)%mod;
           // cout<<tot<<" ";
           // cout<<tar<<" "<<x<<" "<<y<<endl;
		}
        //cout<<endl;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		} 
	}
	//美味预处理 
	
	for(int i=1;i<=n;i++){
		sum[i]=0;
		for(int j=1;j<=m;j++)sum[i]=(sum[i]+a[i][j])%mod;
       // cout<<sum[i]<<" ";
		//tot=tot*sum[i]%mod;
        //上面的代码是错误的。
        //因为总共情况其实还会多出一种：不选。
        tot=tot*(1+sum[i])%mod;
	}
    //cout<<tot<<endl;
    //下面的循环中填的是m不是n。
    //因为是m种主要食材。
	for(int i=1;i<=m;i++)solve(i); 
    //为什么是+mod-1而不是直接+mod
	cout<<(tot+mod-1)%mod<<endl;
	return 0;
}

终于，要写 $100pts$ 的代码了。
经过观察返现最后的几个测试点的范围是 $m\le2000$ 。
这代表我们开不了三维数组。
时间复杂度方面也无法支撑。
这里就需要提一提DP的优化方法了。（其实前面就应该提了，忘了）。
DP的时间复杂度组成： $O(状态*转移)$ 。
那么优化自然也有两类优化：
1.优化状态：可以将两维做差值，压缩成一维（这种方法相当常见，除了本题，相似的还有那个前几天的括号序列）。
2.优化转移：优化转移的方法有很多，可以使用一些普及组算法，比如这道题就使用了前缀和。
那么现在要将 $84pts$ 的做法优化成 $100pts$ 的做法，考虑继续使用优化状态。
其实观察可发现，在这道题中，我们并不关心主要食材和其他食材具体有多少个。
我们只是希望通过知道它们的个数，从而得出它们相差几个，会不会不满足条件。
那么逻辑慢慢清晰。
我们将后两维优化成一维的差值。
也就是说现在是这样的： $dp[i][j[$ 表示有前 $i$ 种烹饪方式，主要食材-其他食材的个数是 $j$ 。
但是问题在于，如何设计状态转移方程？
可以参考前几种做法的状态转移方程。
大概是这样：
1.不做： $dp[i][j]+=dp[i-1][j]$ 。
2.做主要食材的菜： $dp[i][j]+=dp[i-1][j-1]*a[i][k]$ 。
$k$ 是主要食材编号。
3.做其他食材的菜： $dp[i][j]+=dp[i-1][j+1]*(sum[i]-a[i][k])$ 。
然后需要注意一个问题：有没有一张可能，主要食材的数量 $\le$ 其他食材的数量。
那么也就是说， $j\le0$ 。
（虽然说这种情况肯定不会算在“不满足条件”的方案数种）但是，想要求出“不满足条件”的方案数，是需要知道这些情况的数量的。
此时有一个聪明又机智的方法：
直接将 $j$ 加上2000.（2000来源于 $m$ 的范围）。
然后，在计算“不满足条件的方案数”的时候，就去计算大于2000的 $j$ 的数量即可。
差不多了，代码跟84的差不多，甚至更简单。
有问题的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll mod=998244353;
int a[105][2005];
ll sum[2005];
ll tot=1;
ll dp[105][2005];
const int C=2000; 
void solve(int tar){
	//神秘初始化
	dp[0][C]=1; 
	for(int i=1;i<=n;i++){
		for(int j=C-i;j<=i+C;j++){
			dp[i][j]+=dp[i-1][j];
			dp[i][j]=(dp[i][j]+dp[i-1][j-1]*a[i][tar])%mod;
			dp[i][j]=(dp[i][j]+dp[i-1][j+1]*(sum[i]-a[i][tar]))%mod;
		}
	}
	for(int i=C+1;i<=C+n;i++){
		tot=((tot-dp[n][i])%mod+mod)%mod;
        // cout<<tot<<" ";
	}
    //cout<<tot<<endl;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)sum[i]=(sum[i]+a[i][j])%mod;
		tot=tot*(1+sum[i])%mod;
	}
   // cout<<tot<<endl;
	for(int i=1;i<=m;i++)solve(i);
	cout<<(tot+mod-1)%mod;
	return 0;
}

正确的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll mod=998244353;
int a[105][2005];
ll sum[2005];
ll tot=1;
ll dp[105][2005];
const int C=2000; 
void solve(int tar){
	//神秘初始化
	dp[0][C]=1; 
	for(int i=1;i<=n;i++){
		for(int j=C-i;j<=i+C;j++){
			dp[i][j]=dp[i-1][j];
			dp[i][j]=(dp[i][j]+dp[i-1][j-1]*a[i][tar])%mod;
			dp[i][j]=(dp[i][j]+dp[i-1][j+1]*(sum[i]-a[i][tar]))%mod;
		}
	}
	for(int i=C+1;i<=C+n;i++){
		tot=((tot-dp[n][i])%mod+mod)%mod;
        // cout<<tot<<" ";
	}
    //cout<<tot<<endl;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)sum[i]=(sum[i]+a[i][j])%mod;
		tot=tot*(1+sum[i])%mod;
	}
   // cout<<tot<<endl;
	for(int i=1;i<=m;i++)solve(i);
	cout<<(tot+mod-1)%mod;
	return 0;
}