题目：Emiya 家今天的饭
网址：https://www.luogu.com.cn/problem/P5664
这道题质量很高。
算法1 暴力 32pts
首先，观察到对于每一种烹饪方法，我们有两种选择：要么不选任何一道菜（食材），要么任选。
最后判断是否合法即可。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int SIZE = 100 + 5, mod = 998244353;
int n, m, ans = 0, a[SIZE][SIZE], cnt[SIZE];
void dfs(int cur, long long tmp)
{
if(cur == n)
{
int sum = 0, val = 0;
for(int i = 0; i < m; ++ i) sum += cnt[i];
if(!sum) return;
for(int i = 0; i < m; ++ i) val = max(val, cnt[i]);
if(val <= sum / 2) ans = (ans + tmp) % mod;
return;
}
dfs(cur + 1, tmp);
for(int i = 0; i < m; ++ i)
{
if(a[cur][i] == 0) continue;
++ cnt[i];
dfs(cur + 1, tmp * a[cur][i] % mod);
-- cnt[i];
}
return;
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; ++ i)
{
for(int j = 0; j < m; ++ j)
{
scanf("%d", &a[i][j]);
}
}
memset(cnt, 0, sizeof(cnt));
dfs(0, 1ll);
printf("%d
", ans);
return 0;
}
算法2 DP（背包） 64pts
我们将整个问题看成背包。选择次数为容量，最后枚举合法状态。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const long long mod = 998244353;
const long long maxn = 100 + 5, maxm = 10;
long long n, m, a[maxn][4], dp_1[maxn][maxn][maxn], dp_2[maxn][55][55][55];
int main()
{
scanf("%lld %lld", &n, &m);
for(long long i = 1; i <= n; ++ i)
{
for(long long j = 1; j <= m; ++ j)
{
scanf("%lld", &a[i][j]);
}
}
if(m == 2)
{
memset(dp_1, 0, sizeof(dp_1));
dp_1[0][0][0] = 1;
for(long long i = 1; i <= n; ++ i)
{
for(long long j = 0; j <= i; ++ j)
{
for(long long k = 0; k <= i; ++ k)
{
long long &ans = dp_1[i][j][k];
ans = dp_1[i - 1][j][k];
if(j) ans = (ans + dp_1[i - 1][j - 1][k] * a[i][1]) % mod;
if(k) ans = (ans + dp_1[i - 1][j][k - 1] * a[i][2]) % mod;
}
}
}
long long res = 0;
for(long long i = 1; i <= n >> 1; ++ i)
{
res = (res + dp_1[n][i][i]) % mod;
}
printf("%lld
", res);
}
else
{
memset(dp_2, 0, sizeof(dp_2));
dp_2[0][0][0][0] = 1;
for(long long i = 1; i <= n; ++ i)
{
for(long long j = 0; j <= i; ++ j)
{
for(long long k = 0; k <= i; ++ k)
{
for(long long l = 0; l <= i; ++ l)
{
long long &ans = dp_2[i][j][k][l];
ans = dp_2[i - 1][j][k][l];
if(j) ans = (ans + dp_2[i - 1][j - 1][k][l] * a[i][1]) % mod;
if(k) ans = (ans + dp_2[i - 1][j][k - 1][l] * a[i][2]) % mod;
if(l) ans = (ans + dp_2[i - 1][j][k][l - 1] * a[i][3]) % mod;
}
}
}
}
long long sum, res = 0;
for(long long i = 0; i <= n / 2; ++ i)
{
for(long long j = 0; j <= n / 2; ++ j)
{
for(long long k = 0; k <= n / 2; ++ k)
{
if(i + j + k > n || k > i + j) break;
if(i > j + k || j > i + k) continue;
res = (res + dp_2[n][i][j][k]) % mod;
}
}
}
if(!res) puts("0");
else printf("%lld
", res - 1);
}
return 0;
}
正解 DP + 容斥原理
考虑(m>3)的其他情况。注意到选择次数超过(lfloor frac{k}{2} floor)的食材最多有一道。根据容斥原理，我们将所有情况计算出，减去不合法的状态即为所求。
所有情况不难算出，不合法的状态是问题中最关键的一个。
我们只需要枚举该食材即可。
考虑：设(dp[i,j,k,l])代表考虑到第(i)道烹饪方案，食材(j)超过次数，选了(k)个，其余的选了(l)个。
那么有：(dp[i,j,k,l]=dp[i-1.j,k,l]+dp[i-1,j,k-1,l]*a[i,j]+dp[i-1,j,k,l-1]*displaystylesum{a[i,s]})
发现还可以优化：我们其实只关心超过次数与其余次数的差值。则必有：(dp[i,j,k]=dp[i-1,j,k]+dp[i-1,j,k-1]*a[i,j]+dp[i-1,j,k+1]*displaystylesum{a[i,s]})；初始化：(dp[0,1~n,0]=1)（别忘了数组要挪位）。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mod = 998244353;
const int maxn = 100 + 5, maxm = 2000 + 5;
int n, m;
long long ans = 0, a[maxn][maxm], dp[maxn][maxn], g[maxn][maxn << 1], sum[maxn];
int main()
{
scanf("%d %d", &n, &m);
memset(g, 0, sizeof(g));
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; ++ i)
{
for(int j = 1; j <= m; ++ j)
{
scanf("%lld", &a[i][j]);
sum[i] = (sum[i] + a[i][j]) % mod;
}
}
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; ++ i) dp[i][0] = 1;
for(int i = 1; i <= n; ++ i)
{
for(int j = 1; j <= n; ++ j)
{
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * sum[i]) % mod;
}
}
for(int i = 1; i <= n; ++ i) ans = (ans + dp[n][i]) % mod;
for(int k = 1; k <= m; ++ k)
{
memset(g, 0, sizeof(g));
g[0][n] = 1;
for(int i = 1; i <= n; ++ i)
{
for(int j = -n; j <= n; ++ j)
{
g[i][j + n] = (g[i - 1][j + n] + g[i - 1][j + n - 1] * a[i][k] + g[i - 1][j + n + 1] * (sum[i] - a[i][k])) % mod;
}
}
for(int i = n + 1; i <= n << 1; ++ i) ans = (ans + mod - g[n][i]) % mod;
}
printf("%d
", ans);
return 0;
}