Emiya 家今天的饭

\(dp_{i,j,k}\)表示前\(i\)种烹饪方法,假设最多的是食材\(j\)，食材\(j\)比其他食材多\(k\)次出现

其中\(i \in [1,n],j \in [1,m],k \in [-n,n]\)

\(then \Longrightarrow dp_{i,j,k}=dp_{i-1,j,k}+\sum_{l=1}^{m}(l=j?dp_{i-1,j,k-1} :dp_{i-1,j,k+1})\)

本题主要考查滚动数组

总可能(不一定合法)为\(\prod_{i=1}^{n}(1+\sum_{j=1}^{m}a_{i,j})\),

不合法的为\(1\)(没有菜)\(+\sum_{i=1}^{m}\sum_{j=1}^{n}dp_{n,i,j}\)

当然，转移时可以用刷表法，把转移从\(O(m)\)到\(O(1)\)
还有，要开滚动数组(或者用int,只不过打着麻烦些)

\(\mathfrak{talk\ is\ cheap,show\ you\ the\ code}\)

#include<cstdio>
#include<algorithm>
using namespace std;
# define Type template<typename T>
# define read read1<int>()
Type inline T read1()
{
    T t=0;
    bool ty=0;
    char k;
    do k=getchar(),(k=='-')&&(ty=1);while('0'>k||k>'9');
    do t=(t<<3)+(t<<1)+(k^'0'),k=getchar();while('0'<=k&&k<='9');
    return ty?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define ll long long
# define mod 998244353ll
ll dp[2][2003][203];
int s,f[103][2003],m;
ll sum[103];
int main()
{
    //fre("meal");
    s=read,m=read;
    for(int i=0;i++^s;)
        for(int j=0;j++^m;sum[i]%=mod)
            sum[i]+=f[i][j]=read;
    ll ans=1;
    for(int i=0;i++^s;)
        ans=ans*(sum[i]+1)%mod;
    for(int i=0;i++^m;)
        dp[0][i][100]=1;
    for(int i=0;i^s;++i)
        for(int j=0;j++^m;)
            for(int k=-100;k<=100;++k)
                if(dp[i&1][j][k+100])
                {
                    (dp[~i&1][j][k+100]+=dp[i&1][j][k+100])%=mod;
                    (dp[~i&1][j][k+99]+=dp[i&1][j][k+100]*(sum[i+1]-f[i+1][j]))%=mod;
                    (dp[~i&1][j][k+101]+=dp[i&1][j][k+100]*f[i+1][j])%=mod;
                    dp[i&1][j][k+100]=0;
                }
    for(int j=0;j++^m;)
        for(int k=101;k<=200;++k)
            if(dp[s&1][j][k])
                ans=(ans-dp[s&1][j][k])%mod;
    printf("%lld",(ans-1+mod)%mod);
    return 0;
}

Emiya 家今天的饭

原文：https://www.cnblogs.com/SYDevil/p/11900266.html