本题解基于 zzd 大佬的课件。所以写了这篇题解。

题意

给出一个 $n\times m$ 的矩阵（注意位于 $(i,j)$ 的节点可能有多个），要求每行只能选一个节点，每列选的节点不能超过所有选的节点的一半。不能全不选，求总方案数。

结合样例理解：

input:
3 3
1 2 3
4 5 0
6 0 0

output:
190

数据范围：

测试点编号	$n=$	$m=$	$a_{i,j}<$
$1$	$2$	$2$	$2$
$2$	$2$	$3$	$2$
$3$	$5$	$2$	$2$
$4$	$5$	$3$	$2$
$5$	$10$	$2$	$2$
$6$	$10$	$3$	$2$
$7$	$10$	$2$	$10^3$
$8$	$10$	$3$	$10^3$
$9\sim 12$	$40$	$2$	$10^3$
$13\sim 16$	$40$	$3$	$10^3$
$17\sim 21$	$40$	$500$	$10^3$
$22\sim 25$	$100$	$2\times 10^3$	$998244353$

对于所有测试点，保证 $1 \leq n \leq 100$ ， $1 \leq m \leq 2000$ ， $0 \leq a_{i,j} \lt 998,244,353$ 。

点击查看题解

题解

32 pts

递归枚举每一行的选择（注意不选的情况）。~~理论上应该比较好实现~~。递归方式比较奇特。

注意要开 long long，并随时取模（包括后面的 DP）。不然爆 int，~~您会得到 16pts 的好成绩~~。

namespace __32pts
{
	//n 行 m 列，每行只能选一个，每列不能选超过一半 
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=100+10,M=2000+10,mod=998244353;
	ll n,m,a[N][M],cnt[M],ANS=0;
	void dfs(ll step,ll num,ll ans)
	{//step 第几行 num 选的总数 ans 答案 
		if(step>=n+1)
		{
			ll jud=num/2;
			for(ll i=1;i<=m;i++)
				if(cnt[i]>jud) return;
			ANS=(ANS+ans)%mod;
			return;
		}
		dfs(step+1,num,ans);//啥也不选
		for(ll i=1;i<=m;i++)
		{
			if(!a[step][i]) continue;
			cnt[i]++;
			ll nxt=ans*a[step][i]%mod;//一个位置有不同选择
			dfs(step+1,num+1,nxt);//每行只能选一个
			cnt[i]--;
		}
	}
	void main()
	{
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				scanf("%lld",&a[i][j]);
		dfs(1,0,1);
		printf("%lld\n",(ANS-1)%mod);//减去全 0 方案 
		return;
	}
}

48 pts

观察数据， $n=2$ 的情况似乎比较好做。

有一个显然的结论：此时第一列和第二列必定选择相同数量的做菜方法。

设 $f_{i,j,k}$ 表示当前考虑到第 $i$ 行、第一列选了 $j$ 个、第二列选了 $k$ 个的合法方案数。

可以写出状态转移方程：

f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k}\times a_{i,1}+f_{i-1,j,k-1}\times a_{i,2}

namespace __16of48pts
{
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=100+10,M=40+10,mod=998244353;
	ll n,m,a[N][M],ANS=0;
	//第一列和第二列必定选择相同数量的做菜方法
	ll f[N][M][M];//当前枚举到第几行、第一列选了几个、第二列选了几个的答案 
	void main()
	{
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				scanf("%lld",&a[i][j]);
		f[0][0][0]=1;
		for(ll i=1;i<=n;i++)
		{
			for(ll j=0;j<=n;j++)
			{
				for(ll k=0;k<=n;k++)
				{
					if(j>0) f[i][j][k]+=f[i-1][j-1][k]*a[i][1];
					f[i][j][k]%=mod;
					if(k>0) f[i][j][k]+=f[i-1][j][k-1]*a[i][2];
					f[i][j][k]%=mod;
					f[i][j][k]+=f[i-1][j][k];
				}
			}
		}
		for(ll i=1;i<=n/2;i++) ANS=(ANS+f[n][i][i])%mod;
		printf("%lld\n",ANS%mod);
		return;
	}
}

64 pts

此时 $n=3$ 。没关系，仍按照上面的思路即可。

namespace __16of64pts
{
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=100+10,M=40+10,mod=998244353;
	ll n,m,a[N][M],ANS=0;
	ll f[N][M][M][M];//当前枚举到第几行、第一列选了几个、第二列选了几个、第三列选了几个的答案 
	void main()
	{
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				scanf("%lld",&a[i][j]);
		f[0][0][0][0]=1;
		for(ll i=1;i<=n;i++)
		{
			for(ll j=0;j<=n;j++)
			{
				for(ll k=0;k<=n;k++)
				{
					for(ll l=0;l<=n;l++)
					{
						if(j>0) f[i][j][k][l]+=f[i-1][j-1][k][l]*a[i][1];
						f[i][j][k][l]%=mod;
						if(k>0) f[i][j][k][l]+=f[i-1][j][k-1][l]*a[i][2];
						f[i][j][k][l]%=mod;
						if(l>0) f[i][j][k][l]+=f[i-1][j][k][l-1]*a[i][3];
						f[i][j][k][l]%=mod;
						f[i][j][k][l]+=f[i-1][j][k][l];
						f[i][j][k][l]%=mod;
					}
				}
			}
		}
		for(ll i=0;i<=n;i++)
			for(ll j=0;j<=n;j++)
				for(ll k=0;k<=n;k++)
					if(i<=j+k&&j<=i+k&&k<=i+j&&i+j+k<=n)
						ANS+=f[n][i][j][k];
		ANS-=1;
		printf("%lld\n",ANS%mod);
		return;
	}
}

84 pts

之前对 $n=2$ 和 $n=3$ 进行暴力 DP 的思想已经不适用了，我们需要转换一下思想。

注意到本题有一个特点**：不合法的方案的只可能是其中的一列出现问题**。因此我们一列一列来求不合法的方案数，利用容斥原理，先算出总方案数，再减去不合法的方案数。

设 $f_{i,j,k}$ 表示当前考虑到第 $i$ 行、当前列选了 $j$ 个、其他列一共选了 $k$ 个的不合法方案数。需要枚举当前列 $p$ 。

有状态转移方程（其中 $s_i$ 是第 $i$ 行的和）：

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})

namespace __84pts
{
	/*n 行 m 列，每行只能选一个，每列不能选超过一半*/
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=40+10,M=500+10,mod=998244353;
	ll n,m,a[N][M],s[N],tal=1,cnt=0;
	ll f[N][N][N];//当前枚举到第几行，当前列选了几个、其他列选了几个的不合法数 
	ll Mod(ll a){return ((a%mod)+mod)%mod;}
	void main()
	{
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				scanf("%lld",&a[i][j]);
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				s[i]=Mod(s[i]+a[i][j]);
		for(ll i=1;i<=n;i++) tal=Mod(tal*(s[i]+1));
		tal=Mod(tal-1);
		for(ll l=1;l<=m;l++)//枚举列 
		{
			ms(f);f[0][0][0]=1;
			for(ll i=1;i<=n;i++)
			{
				for(ll j=0;j<=i;j++)
				{
					for(ll k=0;k<=i-j;k++)
					{
						f[i][j][k]+=f[i-1][j][k];
						f[i][j][k]=Mod(f[i][j][k]);
						if(j>0) f[i][j][k]+=f[i-1][j-1][k]*a[i][l];
						f[i][j][k]=Mod(f[i][j][k]);
						if(k>0) f[i][j][k]+=f[i-1][j][k-1]*(s[i]-a[i][l]);
						f[i][j][k]=Mod(f[i][j][k]);
					}
				}
			}
			for(ll i=0;i<=n;i++)
				for(ll j=0;j<=i;j++)
				{
					if(i<=j||i+j>n) continue;
					cnt+=f[n][i][j];
					cnt=Mod(cnt);
				}
		}
		printf("%lld\n",Mod(tal-cnt));
		return;
	}
}

100 pts

我们发现，对于 $j$ 和 $k$ 的具体大小我们并不关心，我们只需要表示出当前列比其他列多了多少，于是便可以压缩到一维，用 $j$ 来表示当前列比其他列一共多多少。

由于 $j$ 可能是负数，所以要先加上一个常数再 DP。这就是差值 DP。

状态转移方程如下：

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})

代码

#include<bits/stdc++.h>
using namespace std;
namespace __100pts
{
	/*不合法的只可能有一列。因此我们一列一列来求不合法的方案数，
	利用容斥原理，先算出总方案数，再减去不合法的方案数*/
	/*n 行 m 列，每行只能选一个，每列不能选超过一半*/
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=100+10,M=2000+10,mod=998244353;
	ll n,m,a[N][M],s[N],tal=1,cnt=0;
	ll f[N][N*2];//当前枚举到第几行，当前列比其他列多几个的不合法数 
	ll Mod(ll a){return ((a%mod)+mod)%mod;}
	void main()
	{
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				scanf("%lld",&a[i][j]);
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				s[i]=Mod(s[i]+a[i][j]);
		for(ll i=1;i<=n;i++) tal=Mod(tal*(s[i]+1));
		tal=Mod(tal-1);
		for(ll l=1;l<=m;l++)//枚举列 
		{
			ms(f);f[0][N]=1;
			for(ll i=1;i<=n;i++)
			{
				for(ll j=N-i;j<=N+i;j++)
				{
					f[i][j]+=f[i-1][j];
					f[i][j]=Mod(f[i][j]);
					f[i][j]+=f[i-1][j-1]*a[i][l];
					f[i][j]=Mod(f[i][j]);
					f[i][j]+=f[i-1][j+1]*(s[i]-a[i][l]);
					f[i][j]=Mod(f[i][j]);
				}
			}
			for(ll i=1;i<=n;i++)
			{
				cnt+=f[n][N+i];
				cnt=Mod(cnt);
			}
		}
		printf("%lld\n",Mod(tal-cnt));
		return;
	}
}
int main()
{
	__32pts::main();
	return 0;
}