【CSP2019】Emiya 家今天的饭 | Mrsrz's blog

DP，容斥思想

题目大意：

有 $n$ 种烹饪方法和 $m$ 种主要食材。用第 $i$ 种烹饪方法和第 $j$ 种主要食材可以做出 $a_{i,j}$ 道不同的菜。

现在要做一些菜，必须满足以下条件：

1. 令 $k$ 表示菜的道数。$k\geq 1$。
2. $k$ 道菜的烹饪方法各不相同。
3. 同一种主要食材不得出现在超过 $\lfloor\frac k 2\rfloor$ 道菜中。

问方案数。

题解：

直接做不好求。

观察到第三条限制。发现如果存在一种食材出现超过 $\lfloor\frac k 2\rfloor$ 次，那么别的食材一定不会超过。也就是说最多有一种食材的菜不满足条件。

我们先算出不考虑第三条限制的总方案，可以用背包求，$O(n^2)$。然后减掉违反第三条限制的方案数。

我们枚举主要食材，钦定这个食材违反了条件。

我们需要求出这个食材在多少种方案中违反了条件。

令 $f[i][j]$ 表示前 $i$ 种烹饪方法中，选择当前选定的食材比其余食材多 $j$ 的方案数。

三种转移：要么不选这种烹饪方法，要么选择钦定的食材，要么选择钦定以外的食材。

转移显然是 $O(1)$ 的。

需要减去的是 $\sum\limits_{j>0} f[n][j]$，表示这种菜超过了一半。

对每种钦定的菜的时间复杂度是 $O(n^2)$。

总时间复杂度 $O(n^2m)$。

Code：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=105,M=2005,md=998244353;
typedef long long LL;
int n,m,a[N][M];
int ans,all[N];
struct array{
    int val[N*2];
    inline int&operator[](const int&x){return val[x+103];};
}dp[N];
inline void upd(int&a){a+=a>>31&md;}
void calc_all(){
    int dp[N];
    memset(dp,0,sizeof dp);
    *dp=1;
    for(int i=1;i<=n;++i)
    for(int j=n;j;--j)
    dp[j]=(dp[j]+(LL)all[i]*dp[j-1])%md;
    for(int i=1;i<=n;++i)upd(ans+=dp[i]-md);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        int&x=all[i];
        for(int j=1;j<=m;++j)
        cin>>a[i][j],upd(x+=a[i][j]-md);
    }
    calc_all();
    for(int s=1;s<=m;++s){
        memset(dp,0,sizeof dp);
        dp[0][0]=1;
        for(int i=1;i<=n;++i){
            dp[i]=dp[i-1];
            for(int j=-i;j<=i;++j)
            dp[i][j]=(dp[i][j]+(LL)dp[i-1][j-1]*a[i][s]+(LL)dp[i-1][j+1]*(all[i]-a[i][s]+md))%md;
        }
        for(int j=1;j<=n;++j)
        upd(ans-=dp[n][j]);
    }
    cout<<ans<<'\n';
    return 0;
}