题面

题解

不考虑每种食材不超过一半的限制，答案是

减去 1 是去掉一道菜都不做的方案。

显然只可能有一种菜超过一半，于是枚举这种菜，对每个方式做背包即可（记一维状态表示这种菜比别的菜多做了多少份）。

设dp[i][j]为前i种方法中这种食材比别人多j份，

则 $dp[i][j]=dp[i-1][j+1]*(sum[i] - a[i][j])+dp[i-1][j]+dp[i-1][j-1]*a[i][j]$

于是从零开始枚举j就行了

吗

不对，我们可以意识到dp[i][ - | j |]也对答案有影响，

所以我们设dp[i][n]为原先的dp[i][0]，n以下的是负数情况

#include<cstdio>

#include<iostream>

#include<cstring>

#define LL long long

using namespace std;

int read() {

    int f = 1,x = 0;char s = getchar();

    while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}

    while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}

    return x * f;

}

int mod = 998244353;

int n,m,i,j,s,o,k;

LL a[105][2005];

LL dp[2][205];

LL ans = 0;

int main() {

//  freopen("meal.in","r",stdin);

//  freopen("meal.out","w",stdout);

    n = read();m = read();

    ans = 1;

    for(int i = 1;i <= n;i ++) {

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

            a[i][j] = read();

            a[i][0] += a[i][j];

            a[i][0] %= mod;

        }

        ans = ans * (a[i][0] + 1ll) % mod;

    }

    ans = (ans + mod - 1ll) % mod;

//  printf("%lld\n",ans);

    for(register int k = 1;k <= m;k ++) {

        dp[0][n] = 1;

        for(register int i = 1;i <= n;i ++) {

            for(register int j = n + i;j >= n - i;j --) {

                if(j) dp[i&1][j] = ((dp[1-(i&1)][j + 1] *1ll* (a[i][0] - a[i][k] + mod) % mod) + dp[1-(i&1)][j] + dp[1-(i&1)][j - 1] * a[i][k] % mod) % mod;

                else dp[i&1][j] = ((dp[1-(i&1)][j + 1] *1ll* (a[i][0] - a[i][k] + mod) % mod) + dp[1-(i&1)][j]) % mod;

            }

        }

        for(register int j = n + 1;j <= 2*n;j ++) {

            ans = (ans + mod - dp[n&1][j]) % mod;

            dp[0][j] = 0;

            dp[0][j - n] = 0;

            dp[1][j] = 0;

            dp[1][j - n] = 0;

//          printf("%lld ",dp[n&1][j]);

        }//putchar('\n');

    }

    printf("%lld\n",ans);

    return 0;

}

巴特西

[CSP-S 2019 day2 T1] Emiya家今天的饭

题面

题解

最新文章

热门文章