CSP2019 Emiya今天的饭 题解

$\text{Description}$

给定 $n$ 种烹饪方法,$m$ 种主要食材,使用第 $i$ 种烹饪方法和第 $j$ 道主要食材可以做出 $a_{i,j}$ 种不同的菜。要求你做 $k$ 道菜,满足以下条件:

  1. $k\ge 1$

  2. 每种菜使用的烹饪方法互不相同

  3. 每一种主要食材不出现超过 $\lfloor \dfrac{n}{2}\rfloor$ 次

求方案数对 $998244353$ 取模的值。

$\text{Solution}$

注意到前两个限制比较好处理,我们先计算出满足前两个限制的方案数,再减去不满足第三个限制的方案数即可。

这样的话,我们实际上是在每一种烹饪方法中选一种或零种可做的菜,但如果都选零种显然不符合第一个限制,故要减去 $1$ 。这样的话满足前两个性质的总方案数是:

接下来计算不满足第三个限制但满足前两个限制的方案数,注意到不满足的方案中只会有一种主要食材出现次数超过了一半,所以我们枚举每一种主要食材出现次数超过了一半,然后计算方案数。

考虑当前我们枚举的是第 $x$ 种主要食材,我们令 $f_{i,j,k}$ 表示前 $i$ 种烹饪方法中选了 $j$ 次第 $x$ 种主要食材,选了 $k$ 次别的主要食材的方案,那么有:

$f_{i,j,k}=f_{i-1,j,k-1}\times \sum_{s\neq x} a_{i,s}+f_{i-1,j,k}+f_{i-1,j-1,k}\times a_{i,x}$

目标为 $\sum_{i>j}f_{n,i,j}$

预处理前缀和后,一次动态规划的时间复杂度为 $O(n^3)$,总时间复杂度为 $O(n^3m)$,不大行的样子。

注意到在上面的目标中,我们实际上是求了 $j>k$ 的 $f$ 值。所以考虑将后两维压缩为一维。记 $f_{i,j}$ 表示前 $i$ 种烹饪方法中选了第 $x$ 种主要食材比其它主要食材的次数多了 $j$ 的方案数,那么有:

$f_{i,j}=f_{i-1,j}+f_{i-1,j+1}\times \sum_{s\neq x}a_{i,s}+f_{i-1,j-1}\times a_{i,x}$

由于作差会出现负值,用一个 $\text{Naive}$ 的 $\text{Trick}$ ,在第二维手动加值即可。这样的话优化掉了一维,总时间复杂度降低为 $O(n^2m)$。

$\text{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define REG register
#define MOD 998244353
#define MAXN 110
#define LL long long
using namespace std;
inline int read(){
REG int x(0);
static char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
return x;
}
inline int Add(int a,int b){return a+b>MOD?a+b-MOD:a+b;}
inline int Del(int a,int b){return a-b<0?a-b+MOD:a-b;}

int n,m;
int sum[MAXN];
int ans;
int f[MAXN][MAXN<<1],a[MAXN][2005];

inline void Init(){
n=read(),m=read();
for(REG int i=1;i<=n;++i)
for(REG int j=1;j<=m;++j)
a[i][j]=read(),sum[i]=Add(sum[i],a[i][j]);
ans=1;
for(REG int i=1;i<=n;++i)
ans=(LL)Add(sum[i],1)*ans%MOD;
ans=Del(ans,1);
}

inline int Calc(int x){
memset(f,0,sizeof f);
f[0][n]=1;
for(REG int i=1;i<=n;++i)
for(REG int j=n-i;j<=n+i;++j){
f[i][j]=f[i-1][j];
f[i][j]=Add(f[i][j],(LL)f[i-1][j-1]*a[i][x]%MOD);
f[i][j]=Add(f[i][j],(LL)f[i-1][j+1]*Del(sum[i],a[i][x])%MOD);
}
int res(0);
for(REG int i=1;i<=n;++i) res=Add(res,f[n][n+i]);
return res;
}

int main(){
Init();
for(REG int i=1;i<=m;++i)
ans=Del(ans,Calc(i));
printf("%d\n",ans);
}
#
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×