题意

Emiya 会 n 种烹饪方法和处理 m 种主要食材。Emiya 做菜一定会用一种烹饪方法和一种主要食材,具体地,用第 i 种方法处理 j 号主要食材可以做出 a_{i,j} 种菜。现在他要做 k 道菜,需要满足:

  • $k\ge1$
  • 每道菜的烹饪方法互不相同
  • 每种主要食材最多使用 \lfloor k/2\rfloor

求所有满足要求的做菜方案数。

思路

分析题意

注意到 k 至少为 2,然后第二个要求非常好处理,而第三个要求比较困难。

正难则反,先求出一共能做出多少种搭配,然后减去不合法的方案即可。由加法原理和乘法原理知一共能做出来的即为 \displaystyle\prod_{i=1}^n(\sum_{j=1}^ma_{i,j}+1)-1。(减去的 1 为什么都不做)

接下来就可以考虑怎么处理第三个要求了

84pts 做法

然后,我们可以发现不满足要求的食材有且仅有一样(显然),所以可以枚举这个不满足要求的食材,然后进行 dp 求解。

f_{i,j,k} 为正在处理第 p 样食材,考虑前 i 个方法,使用其余食材做了 j 道菜,用第 p 样食材做了 k 道菜的方案数。

则由乘法原理和加法原理得到

f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k}\times (s_i-a_{i,p})+f_{i-1,j,k-1}\times a_{i,p}

其中 s_i=\sum_j a_{i,j}

然后只需要枚举 jk 并减掉不合要求的方案数即可。

代码:

#include <cstdio>
#include <cctype>
#include <cstring>

...

ll a[maxn][maxm],s[maxn];//n 方法,m食材
ll ans=1;
ll f[maxn][maxn][maxn];//考虑到第 a 种食材,前 i 种方法,其余做了 j 道菜,剩下 k 道是用当前食材做的

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
            a[i][j]=read(),s[i]=(s[i]+a[i][j])%mod;
        ans=ans*(s[i]+1)%mod;
    }
    ans=(ans-1ll)%mod;//先减掉全部选的方案
    for(int gg=1;gg<=m;++gg)//枚举每一种食材
    {
        memset(f,0,sizeof f);
        f[0][0][0]=1;//边界
        for(int i=1;i<=n;++i)
            for(int j=0;j<=n;++j)
                for(int k=0;k<=n;++k)
                {
                    if(j+k>i)break;
                    ll tmp1=0,tmp2=0,tmp3=0;
                    tmp1=f[i-1][j][k];
                    if(j>0)//防止访问负下标而 RE
                        tmp2=f[i-1][j-1][k]*(s[i]-a[i][gg])%mod;
                    if(k>0)//防止访问负下标而 RE
                        tmp3=f[i-1][j][k-1]*a[i][gg]%mod;
                    f[i][j][k]=tmp1+tmp2+tmp3;f[i][j][k]%=mod;
                }
        ll tmp=0;//记录不合法方案数
        for(int i=0;i<=n;++i)
            for(int j=0;j<=n;++j)
            {
                ll tot=i+j;
                if(tot>n)break;
                if(j<=(tot>>1))continue;
                tmp+=f[n][i][j],tmp%=mod;
            }
        ans=(ans-tmp+mod)%mod;//取模注意防止负数出现
    }
    printf("%lld\n",ans);
    return 0;
}

满分做法

考虑优化之前 O(n^3m) 的 dp,注意到我们如果想要判断一个方案合不合法,根本就不需要知道 jk 具体的值,只需知道用 p 做出来的菜比其他的多多少,只要这个差量 \Delta>0,说明就是不合法的。

定义 f_{i,j} 为考虑前 i 种烹饪方法,用 p 做出来菜的数量比用其他菜做的数量多 j 道的方案数,$j$ 可能为负,需要防止数组越界

转移方程:

f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times a_{i,p}+f_{i-1,j+1}\times(s_i-a_{i,p})

最后不合法的方案数就是 \sum_{j>0}f_{n,j}

#include <cstdio>
#include <cctype>
#include <cstring>
#define f(i,j) f[i][j+maxn]

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

typedef long long ll;
const int maxn=100+5,maxm=2000+5;
const int mod=998244353;

int n,m;
ll a[maxn][maxm],s[maxn];//n 方法,m食材
ll ans=1;
ll f[maxn][maxn<<1];

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
            a[i][j]=read(),s[i]=(s[i]+a[i][j])%mod;
        ans=ans*(s[i]+1)%mod;
    }
    ans=(ans-1ll)%mod;
    for(int gg=1;gg<=m;++gg)
    {
        memset(f,0,sizeof f);
        f(0,0)=1;
        for(int i=1;i<=n;++i)
            for(int j=-i;j<=i;++j)
                f(i,j)=(f(i-1,j)+f(i-1,j-1)*a[i][gg]+f(i-1,j+1)*(s[i]-a[i][gg]))%mod;
        for(int j=1;j<=n;++j)
            ans=(ans-f(n,j)+mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改日期:2020年12月2日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。