P5664

Aryper · 2021-11-14 13:59:48 · 个人记录

[CSP-S2019] Emiya 家今天的饭

容斥 DP。

今天再回过头来看一遍。

首先定义状态 f(i,j) 表示前 i 种烹饪方法中选择 j 种的方案数。

然后 \sum_{1\le i\le n} f(n,i) 就是总方案数。

再定义 f(i,j) 表示对于第 p 种食材，前 i 种烹饪方法中，当前列选的数目比其他列的总和多 j 种

然后这里就会有转移方程：

然后就做完了。

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

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<vector>
using namespace std;

long long n,m,sum,nl,ans;

long long a[105][2005],f[105][205],s[105];

const long long mo=998244353;

int main() {

    cin>>n>>m;

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%lld",&a[i][j]);
            s[i]=(s[i]+a[i][j])%mo;
        }
    }

    f[0][0]=1; 

    for(int i=1;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            if(j>0)
            f[i][j]=(f[i-1][j]+s[i]*f[i-1][j-1]%mo)%mo;
            else
            f[i][j]=f[i-1][j];
        }
    }

    for(int i=1;i<=n;i++) {
        sum=(sum+f[n][i])%mo;
    }

    memset(f,0,sizeof(f));

    for(int p=1;p<=m;p++) {

        f[0][n]=1;
        for(int i=1;i<=n;i++) {
            for(int j=n-i;j<=n+i;j++) {
                f[i][j]=(f[i-1][j]+f[i-1][j-1]*a[i][p]%mo+f[i-1][j+1]*(s[i]-a[i][p])%mo)%mo;
            }
        }

        for(int i=1;i<=n;i++) {
            nl=(nl+f[n][n+i])%mo;
        }
    }

    ans=(sum-nl+mo)%mo;

    printf("%lld",ans%mo);

    return 0;
}