$\text{Description}$
给定 $n$ 种烹饪方法，$m$ 种主要食材，使用第 $i$ 种烹饪方法和第 $j$ 道主要食材可以做出 $a_{i,j}$ 种不同的菜。要求你做 $k$ 道菜，满足以下条件：
$k\ge 1$
每种菜使用的烹饪方法互不相同
每一种主要食材不出现超过 $\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);
}
|
