题解"/>
P5664 Emiya 家今天的饭 题解
博客园同步
原题链接
简要题意:
对每种菜有对应的若干种烹饪方法,用二维矩阵表示。求:每种食材用不超过 ⌊ k 2 ⌋ \lfloor \frac{k}{2} \rfloor ⌊2k⌋ 次,至少炒一道菜,烹饪方法互不相同的个数。
算法一
注意到,对于 32 % 32 \% 32% 的数据, n ≤ 10 n \leq 10 n≤10, m ≤ 3 m \leq 3 m≤3.
这部分我们可以试试暴力。
暴力的注意点是,烹饪方法是独立的,因此对每个烹饪方法进行分别计算。
具体见代码。
时间复杂度: O ( ( m + 1 ) n ) O((m+1)^n) O((m+1)n).
实际得分: 32 p t s 32pts 32pts.
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;const int N=2e3+1;
const int MOD=998244353;
typedef long long ll;inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}int h[N],n,m; //h[i] 表示烹饪方法的选择种数
ll ans=0; int a[N][N];inline void dfs(int dep,int sum,int x,int y) {// dep 是正在决策的一行(即烹饪方法),sum 是方案数,x 是要选的行数,y 是已选的行数if(x==y) {ans=(ans+sum)%MOD; return;} if(dep>n) return;for(int i=1;i<=m;i++)if(h[i]+1<=x/2) { //要求不超过一半h[i]++;dfs(dep+1,(1ll*sum*a[dep][i])%MOD,x,y+1); //乘法原理h[i]--; //注意减回去,不要影响回溯} dfs(dep+1,sum,x,y); //否则不选
}int main(){n=read(),m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) a[i][j]=read();if(n<=10) {for(int i=2;i<=n;i++) dfs(1,1,i,0); //对每个烹饪方法分别计算printf("%lld\n",ans); return 0;} //第一档部分分return 0;
}
算法二
注意到, m = 2 m=2 m=2 且 n = 40 n=40 n=40 是一个部分分。
这时,每种烹饪方法只有 3 3 3 种:不选,选第 1 1 1 个,选第 2 2 2 个。(不可以都选,因为不能超过 ⌊ m 2 ⌋ \lfloor \frac{m}{2} \rfloor ⌊2m⌋).
此时这就是背包。
即把 a i , j a_{i,j} ai,j 当成价值,然后有 2 2 2 个物品, 40 40 40 种选法即可。
用 f i , j , k f_{i,j,k} fi,j,k 表示前 i i i 种烹饪方法,第一个物品选了 j j j 种,第二个选了 k k k 种的方案数。
则:
f i , j , k = f i − 1 , j , k + f i − 1 , j − 1 , k × a i , 1 + f i − 1 , j , k − 1 × a i , 2 f_{i,j,k} = f_{i-1,j,k} + f_{i-1,j-1,k} \times a_{i,1} + f_{i-1,j,k-1} \times a_{i,2} fi,j,k=fi−1,j,k+fi−1,j−1,k×ai,1+fi−1,j,k−1×ai,2
注意处理取模,负下标的细节。
时间复杂度: O ( n 3 ) O(n^3) O(n3).
实际得分: 48 p t s 48pts 48pts.
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;const int N=1e2+1;
const int MOD=998244353;
typedef long long ll;inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}int h[N],n,m; //h[i] 表示烹饪方法的选择种数
ll ans=0; int a[N][N];
ll f[N][N][N];inline void dfs(int dep,int sum,int x,int y) {// dep 是正在决策的一行(即烹饪方法),sum 是方案数,x 是要选的行数,y 是已选的行数if(x==y) {ans=(ans+sum)%MOD; return;} if(dep>n) return;for(int i=1;i<=m;i++)if(h[i]+1<=x/2) { //要求不超过一半h[i]++;dfs(dep+1,(1ll*sum*a[dep][i])%MOD,x,y+1); //乘法原理h[i]--; //注意减回去,不要影响回溯} dfs(dep+1,sum,x,y); //否则不选
}int main(){n=read(),m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) a[i][j]=read();if(n<=10) {for(int i=2;i<=n;i++) dfs(1,1,i,0); //对每个烹饪方法分别计算printf("%lld\n",ans); return 0;} //第一档部分分if(n<=40 && m<=2) {f[0][0][0]=1; ans=0;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)for(int k=0;k<=i;k++) {f[i][j][k]=f[i-1][j][k]; //首先考虑不选if(j) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*a[i][1])%MOD; //选第一个if(k) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*a[i][2])%MOD; //选第二个} for(int i=1;i<=n/2;i++) ans=(ans+f[n][i][i])%MOD; //因为都不能超过 n/2,所以只能都等于;如果小于 n/2 则另一个大于 n/2,不可以printf("%lld\n",ans); return 0;}return 0;
}
算法三
然后我们发现, n = 40 n=40 n=40, m = 3 m=3 m=3 本质和 m = 2 m=2 m=2 区别不大。
此时 ⌊ 3 2 ⌋ = 1 \lfloor \frac{3}{2} \rfloor = 1 ⌊23⌋=1,因此还是最多只能选一个。
同样的,用 g i , j , k , l g_{i,j,k,l} gi,j,k,l 表示前 i i i 种烹饪方法,第一个物品选了 j j j 种,第二个选了 k k k 种,第三个选了 l l l 种。
则:
g i , j , k , l = g i − 1 , j , k , l + g i − 1 , j − 1 , k , l × a i , 1 + g i − 1 , j , k − 1 , l × a i , 2 + g i − 1 , j , k , l − 1 × a i , 3 g_{i,j,k,l}=g_{i-1,j,k,l} + g_{i-1,j-1,k,l} \times a_{i,1} + g_{i-1,j,k-1,l} \times a_{i,2} + g_{i-1,j,k,l-1} \times a_{i,3} gi,j,k,l=gi−1,j,k,l+gi−1,j−1,k,l×ai,1+gi−1,j,k−1,l×ai,2+gi−1,j,k,l−1×ai,3
仍然注意处理取模,负下标的问题。
时间复杂度: O ( n 4 ) O(n^4) O(n4).
实际得分: 64 p t s 64pts 64pts.
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;const int N=4e1+1;
const int MOD=998244353;
typedef long long ll;inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}int h[N],n,m; //h[i] 表示烹饪方法的选择种数
ll ans=0; int a[N][N];
ll f[N][N][N];
ll g[N][N][N][N];inline void dfs(int dep,int sum,int x,int y) {// dep 是正在决策的一行(即烹饪方法),sum 是方案数,x 是要选的行数,y 是已选的行数if(x==y) {ans=(ans+sum)%MOD; return;} if(dep>n) return;for(int i=1;i<=m;i++)if(h[i]+1<=x/2) { //要求不超过一半h[i]++;dfs(dep+1,(1ll*sum*a[dep][i])%MOD,x,y+1); //乘法原理h[i]--; //注意减回去,不要影响回溯} dfs(dep+1,sum,x,y); //否则不选
}int main(){n=read(),m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) a[i][j]=read();if(n<=10) {for(int i=2;i<=n;i++) dfs(1,1,i,0); //对每个烹饪方法分别计算printf("%lld\n",ans); return 0;} //第一档部分分if(n<=40 && m==2) {f[0][0][0]=1; ans=0;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)for(int k=0;k<=i;k++) {f[i][j][k]=f[i-1][j][k]; //首先考虑不选if(j) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*a[i][1])%MOD; //第一个 if(k) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*a[i][2])%MOD; //第二个 } for(int i=1;i<=n/2;i++) ans=(ans+f[n][i][i])%MOD;//因为都不能超过 n/2,所以只能都等于;如果小于 n/2 则另一个大于 n/2,不可以printf("%lld\n",ans); return 0;}if(n<=40 && m==3) {g[0][0][0][0]=1; ans=0;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)for(int k=0;k<=i;k++)for(int l=0;l<=i;l++) {g[i][j][k][l]=g[i-1][j][k][l]; //首先考虑不选if(j) g[i][j][k][l]=(g[i][j][k][l]+g[i-1][j-1][k][l]*a[i][1])%MOD; //第一个if(k) g[i][j][k][l]=(g[i][j][k][l]+g[i-1][j][k-1][l]*a[i][2])%MOD; //第二个if(l) g[i][j][k][l]=(g[i][j][k][l]+g[i-1][j][k][l-1]*a[i][3])%MOD; //第三个} for(int i=0;i<=n/2;i++) //这时三个没有大小关系,不确定,因此需要枚举for(int j=0;j<=n/2;j++)for(int k=0;k<=n/2;k++) {if(i>j+k || j>i+k || k>i+j) continue; //超过另外两个说明大于 n/2 (类似于三角形三边)ans=(ans+g[n][i][j][k])%MOD;} printf("%lld\n",ans-1); return 0; //此时 g[n][0][0][0] 被算了一次,需要减去}return 0;
}
算法四
下面是满分算法。(如果想看 84 p t s 84pts 84pts 的部分分,下面也有说明)
考虑容斥,把所有方案加上,然后 dp \texttt{dp} dp 求出不合法的方案数。
这时我们需要抛开所有的前面所说。
用 f i , j , k f_{i,j,k} fi,j,k 表示前 i i i 种菜选 j j j 种烹饪方法,且当前烹饪方法选 k k k 次的方案数。
但是这样显然不能得到满分,考虑状态的简化。
限制为 k > ⌊ j 2 ⌋ k > \lfloor \frac{j}{2} \rfloor k>⌊2j⌋,推一步等到:
2 k + n − j > n 2k + n - j > n 2k+n−j>n. (为什么要同时 + n +n +n?后面你就明白了)
而 n − j n-j n−j 正是该方法不选的哪些菜。所以考虑简化。
对于每种烹饪方法,选它时当做选 2 2 2 次,不做当做选 1 1 1 次。最后的方案数,就是被选超过 n n n 次的方案。
这个转移很妙,此时我们就不用枚举前 i i i 种菜选的烹饪方法,只考虑当前方法即可。
所以 j j j 这一维被省略(降维)。
时间复杂度: O ( n 2 × m ) O(n^2 \times m) O(n2×m).
实际得分: 100 p t s 100pts 100pts.
#include<bits/stdc++.h>
using namespace std;const int N=200,M=3000,MOD=998244353;
typedef long long ll;inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}int n,m;
ll ans=1,s[N],a[N][M],f[N][M];
// s[i] 是第 i 中烹饪方法的方案和
// 如果不降掉第二维,则只有 84 分int main(){n=read(),m=read();for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {a[i][j]=read();s[i]=(s[i]+a[i][j])%MOD;} ans=(ans*(s[i]+1))%MOD;} ans=(ans+MOD-1)%MOD; //所有方案,减去全部不选for(int i=1;i<=m;i++) {memset(f,0,sizeof(f)); f[0][0]=1;for(int j=1;j<=n;j++)for(int k=0;k<=((j-1)<<1);k++) {f[j][k]=(f[j][k]+f[j-1][k]*(s[j]-a[j][i]))%MOD; //不选当前列,继承前面的列f[j][k+1]=(f[j][k+1]+f[j-1][k])%MOD; //不选当前烹饪方法,继承上一个方法f[j][k+2]=(f[j][k+2]+f[j-1][k]*a[j][i])%MOD; //选 a[j][i] 这个点}for(int j=n+1;j<=(n<<1);j++) ans=(ans+MOD-f[n][j])%MOD; //减去答案,注意取模} printf("%lld",ans);return 0;
}
更多推荐
P5664 Emiya 家今天的饭 题解
发布评论