CSP2019 Emiya 家今天的饭 题解

这题在考场上只会O(n^3 m),拿了84分。。

先讲84分，考虑容斥，用总方案减去不合法方案，也就是枚举每一种食材，求用它做超过\(\lfloor \frac{k}{2} \rfloor\) 道菜的方案数，从总方案中减去。

先枚举一种食材x，设f[i][j][k]为前i种烹饪方法中，做j道菜，其中k道是食材x做的的方案数，转移考虑第i种烹饪方案 不做菜/做食材x的菜/做其他食材的菜 三种情况。最后所有f[n][j][j/2+1 ~ n]的和即是不合法情况。

考虑怎么优化，设一种方案中有k道菜，其中t道菜是x食材做的，那么当且仅当\(t>\lfloor \frac{k}{2}\rfloor\)时方案不合法，也即\(2t-k>0\)时不合法。那么我们在dp时就只需要记录方案中\(2t-k\)的值，最后取大于0的状态的方案数即可。即设f[i][j]为只考虑前i种烹饪方法，方案中\(2t-k\)的值为j的方案数。转移考虑以上三种情况分别转移到 f[i+1][j]/f[i+1][j+1]/f[i+1][j-1] 即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define N 107

#define M 2007

#define ll long long

const ll mod=998244353;

ll a[N][M],sum[N],f[N][N<<1];

int main()

{

	int n,m;

	scanf("%d%d",&n,&m);

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

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

		{

			scanf("%lld",&a[i][j]);

			sum[i]=(sum[i]+a[i][j])%mod;

		}

	ll ans=0;

	for(int now=1;now<=m;now++)

	{

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

		f[0][N]=1;

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

		{

			for(int j=N-n;j<=N+n;j++)

			{

				f[i][j]=(f[i][j]+f[i-1][j])%mod;

				f[i][j]=(f[i][j]+f[i-1][j-1]*a[i][now])%mod;

				f[i][j]=(f[i][j]+f[i-1][j+1]*(sum[i]+mod-a[i][now]))%mod;

			}

		}

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

			ans=(ans+f[n][N+i])%mod;

	}

	ll res=1;

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

		res=res*(sum[i]+1)%mod;

	res=(res+mod-1)%mod;

	res=(res+mod-ans)%mod;

	printf("%lld\n",res);

	return 0;

}