题目链接
https://www.luogu.com.cn/problem/P5664
题解
正着递推发现并不好计算，我们可以考虑补集转化，计算不满足条件的方案数。
先计算总方案数，设 \(g_{i,j}\) 代表前 \(i\) 行选 \(j\) 道菜的方案数，\(s_i\) 代表第 \(i\) 行的总菜品数，显然有：
$$g_{i,j}=g_{i-1,j}+g_{i-1,j-1} \times s_i$$
容易发现最多只有一列会被选择超过一半次，因此我们可以枚举不合法的列进行递推。
设第 \(p\) 列为不合法的列，\(f_{i,j,k}\) 表示前 \(i\) 行，第 \(p\) 列选了 \(j\) 道菜，其他列选了 \(k\) 道菜的方案数。
则有如下转移方程：
$$f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k} \times a_{i,p}+f_{i-1,j,k-1} \times (s_i-a_{i,p})$$
所有满足 \(j>k\) 的 \(f_{n,j,k}\) 都会计入不合法的方案数。最后用总方案数减去所有总不合法方案数即可得到合法方案数的总数。
单次递推时间复杂度为 \(O(n^3)\)，需要枚举 \(m\) 列，因此总时间复杂度为 \(O(mn^3)\)，可以拿到 88 分。
实际上，\(j,k\) 的具体数值我们并不太在意，只有它们的差值是关键的。因此我们可以设 \(f_{i,j}\) 表示在前 \(i\) 行内，指定列比其他列多 \(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})$$
这样就可以将时间复杂度优化到 \(O(mn^2)\)。
#include <cstring>
#include <iostream>
#define MOD 998244353
using namespace std;
long long f[105][205],g[105][105],s[105],a[105][2005];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
s[i]=(s[i]+a[i][j])%MOD;
}
g[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
g[i][j]=(g[i-1][j]+g[i-1][j-1]*s[i])%MOD;
long long ans=0;
for(int i=1;i<=n;i++)
ans=(ans+g[n][i])%MOD;
for(int p=1;p<=m;p++)
{
memset(f,0,sizeof(f));
f[0][n+1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=2*n+1;j++)
f[i][j]=(f[i-1][j]+f[i-1][j-1]*a[i][p]%MOD+f[i-1][j+1]*(s[i]-a[i][p]+MOD)%MOD)%MOD;
for(int i=1;i<=n;i++)
ans=(ans-f[n][n+1+i])%MOD;
}
cout<<(ans+MOD)%MOD<<endl;
return 0;
}