题意
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}
然后只需要枚举 j 和 k 并减掉不合要求的方案数即可。
代码：
#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，注意到我们如果想要判断一个方案合不合法，根本就不需要知道 j 和 k 具体的值，只需知道用 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;
}
留言