题解：P5664 [CSP-S2019] Emiya 家今天的饭

· · 题解

题目大意

给你一个 n\times m 的矩阵 a，a_{i,j} 表示在第 i 种烹饪方式下用第 j 种原料能做出 a_{i,j} 道菜，然后给你三个条件。

设 Emiya 会做 k 道菜。

求出方案数对 998,244,353 取模的结果。

解题思路

首先分析条件。

这个没啥好说的。

即每行只能选一个菜。

即每一列选的菜的个数不超过一半的菜。

这是本题的重点。

我们可以考虑容斥，用总方案数减去任意一列选的菜数大于总菜数的一半的方案数就是答案了，接下来分开考虑。

总方案数

设 sum_i=\sum^m_{j=1}a_{i,j}。

因为每一行只能选一个或不选，所以第 i 行的方案数为 sum_i+1，但是必须至少做一道菜，所以 ans=(\prod^{n}_{i=1}sum_i)-1。

long long o=1;
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;
    }
    o=o*(sum[i]+1)%mod;
}
o=(o-1+mod)%mod;

任意一列选的菜数大于总菜数的一半的方案数

有点绕。

设 k 为烹饪的的总菜数。

如果有一个原料选的菜数大于 \lfloor\frac{k}{2}\rfloor，那么其他的菜便不可能大于 \lfloor\frac{k}{2}\rfloor。

所以我们可以枚举是哪一个原料做的菜大于 \lfloor\frac{k}{2}\rfloor 了。

我们发现我们只关心这个原料做的菜是否大于 \lfloor\frac{k}{2}\rfloor，而不关心到底做了多少个。

所以考虑差值 dp，对于食材 c ，设 f_{i,j} 表示考虑了前 i 个烹饪方法，第 c 个食材做了多少个菜与其他食材做了多少个菜的差为 j 的方案数。

由于第 c 个食材的菜数大于 \lfloor\frac{k}{2}\rfloor，所以如果 j>0，那么就代表第 c 个食材的菜数大于 \lfloor\frac{k}{2}\rfloor 了。（感性理解）

考虑怎么从 i-1 转移到 i。

首先如果第 i 种烹饪方式不选，那么 j 不变，就有 f_{i-1,j}\Rightarrow f_{i,j}。

如果选了第 c 种原材料，那么 j 就会加一，但是你就算选第 c 种原材料也有 a_{i,c} 种选法，于是有 f_{i-1,j-1}\times a_{i,c}\Rightarrow f_{i,j}。

如果没选第 c 种原材料，那么 j 就会减一，会有 sum_i-a_{i,c} 种选法，于是有 f_{i-1,j+1}\times (sum_i-a_{i,c})\Rightarrow f_{i,j}。

所以转移方程为：

f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times a_{i,c}+f_{i-1,j+1}\times (sum_i-a_{i,c})

但是又由于 j 有可能是负数，所以我们整体加上 n 就不会数组越界了。

code

#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
long long n,m,ans;
long long f[101][301];
long long sum[101];
long long g[201][201];
long long a[201][2001];
int main()
{
    cin>>n>>m;
    long long o=1;//总方案数
    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;
        }
        o=o*(sum[i]+1)%mod;
    }
    o=(o-1+mod)%mod;
    for(int ch=1;ch<=m;ch++)
    {
        memset(f,0,sizeof(f));//每一个原材料单独求
        f[0][n]=1;//全体加n
        for(int i=1;i<=n;i++)
        {
            for(int j=n-i;j<=n+i;j++)//在i时最少会到n-i,最多会到n+i
            {
                f[i][j]=(f[i-1][j]+f[i-1][j-1]*a[i][ch]%mod+f[i-1][j+1]*(sum[i]+mod-a[i][ch])%mod)%mod;
            }
        }
        for(int i=1;i<=n;i++)//统计答案
        {
            ans=(ans+f[n][i+n])%mod;
        }
    }
    cout<<(o-ans+mod)%mod;//容斥
    return 0;
}