洛谷 P5664 [CSP-S2019] Emiya 家今天的饭

链接：

题意：

给出一个 \(n*m\) 的矩阵 \(a\)，选 \(k\) 个格子（\(1\leq k\leq n\)），每行最多选一个，每列最多选\(⌊\dfrac k2⌋\) 个，同时每个格子有 \(a_{i,j}\) 种不同选法，问共有多少种不同的选法，对 \(998244353\) 取模。给出 \(n,m\) 和矩阵 \(a\)。

分析：

尝试直接 dp 失败后看了题解。这是道 dp 和容斥的好题。

考虑列的限制，每列最多选\(⌊\dfrac k2⌋\) 个，意味着最多只有一列不合法，所以我们可以枚举不合法的列，似乎能更容易地算出不合法的方案数。

所以考虑算出不计列限制的方案数，减去列限制不合法的方案数来容斥得到答案。

算法：

对于列限制不合法的方案数。

首先枚举不合法的列数 \(c\)。

dp 的设计很巧妙，由于我们只关心第 \(c\) 列，其他列之间的区别不重要，所以将其他列融合成一个状态。设 \(f[i,j,k]\) 为前 \(i\) 行，第 \(c\) 列选了 \(j\) 个，其他列选了 \(k\) 个的方案数。

分成第 \(i\) 行不选，选第 \(c\) 列，选其他列来转移。

选第 \(c\) 列的方案有 \(a_{i,c}\) 种，则选其他列的方案有 \(\sum\limits_{j=1}^m a_{i,j}-a_{i,c}\) 种，所以我们需要用一个 \(s\) 数组预处理第 \(i\) 行所有 \(a\) 之和。

\(f[i,j,k]=f[i-1,j,k]+a_{i,c}*f[i-1,j-1,k]+(s_i-a_{i,c})*f[i-1,j,k-1]\)

最后的答案要满足第 \(c\) 列不合法且至少选一个，所以是 \(\sum\limits_{j=1}^n\sum\limits_{k=0}^{\min(j-1,n-j)}f[n,j,k]\)。（\(j-1\) 保证 \(j>k\) ，\(n-j\) 保证 \(j+k\leq n\)）

初值是 \(f[0,0,0]=1\)，状态数是 \(n^3\) 枚举了 \(m\) ，所以时间复杂度是 \(O(n^3m)\)。

对于不计列限制的方案数。

只限制每行最多选一个，我们可以运用组合数学，每行的方案数是 \(s_i+1\) （选或不选），所以只用把所有 \(s_i+1\) 乘起来，又因为 \(k\geq1\) ，所以最后减掉一个完全没有选的方案即可。即 \(\prod\limits_{i=1}^n(s_i+1)-1\)。

时间复杂度 \(O(n)\)。

优化：

上面的算法时间复杂度 \(O(n^3m)\)，可以获得84分的好成绩。

于是对于列限制不合法的 dp 又有了一个更神仙的优化：我们发现要判断不合法方案不需要 \(j\) 和 \(k\) 的具体数值而只需要他们的相对大小，所以将“第 \(c\) 列选了 \(j\) 个，其他列选了 \(k\) 个”的状态再融合成"第 \(c\) 列比其他列多选 \(j\) 个"，那么状态转移方程变为\(f[i,j]=f[i-1,j]+a_{i,c}*f[i-1,j-1]+(s_i-a_{i,c})*f[i-1,j+1]\)。

由于 \(j\) 会有负数的情况，所以将 dp 第二维参与操作时全部加上 \(n\)。

初值是 \(f[0,0+n]=1\)，时间复杂度降为 \(O(n^2m)\)，可以通过此题。

代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define in read()

inline int read(){

	int p=0,f=1;

	char c=getchar();

	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}

	return p*f;

}

const int mod=998244353;

int n,m;

int a[105][2005];

int s[105];

int f[105][205];

int ans1,ans2;

inline int add(int a,int b){return (a+b)%mod;}

inline int mul(int a,int b){return a*b%mod;}

signed main(){

	n=in,m=in;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++){

			a[i][j]=in;

			s[i]=add(s[i],a[i][j]);

		}

	for(int c=1;c<=m;c++){

		memset(f,0,sizeof(f));

		f[0][n+0]=1;

		for(int i=1;i<=n;i++)

			for(int j=-i;j<=i;j++){

				f[i][n+j]=f[i-1][n+j];

				if(j>-i)f[i][n+j]=add(f[i][n+j],mul(f[i-1][n+j-1],a[i][c]));

				if(j<i)f[i][n+j]=add(f[i][n+j],mul(f[i-1][n+j+1],((s[i]-a[i][c])%mod+mod)%mod));

			}

		for(int j=1;j<=n;j++)

				ans1=add(ans1,f[n][n+j]);

	}

	ans2=1;

	for(int i=1;i<=n;i++)

		ans2=mul(ans2,s[i]+1);

	ans2-=1;

	cout<<((ans2-ans1)%mod+mod)%mod;

	return 0;

}

题外话：

这个 dp 加容斥好难啊我趣

巴特西

洛谷 P5664 [CSP-S2019] Emiya 家今天的饭

链接：

题意：

分析：

算法：

优化：

代码：

题外话：

最新文章

热门文章