记录编号	547287	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2019S]Emiya家今天的饭	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	4.259 s
提交时间	2019-11-29 01:25:44	内存使用	6.58 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long int
using namespace std;
int dp1[101][2001];//dp1[i][j]前i种方法对于特定食材X而言使用X制作的菜比使用其他原料的菜多j道 
//每次枚举一个特定食材X
//也就是说对于每一种食材,不合法答案是dp1[n][1---n];
//因为j的意义为差值，因此有负数,最小加上n即可消去负数 
int dp2[101][2001];//dp2保存不考虑限制的情况下在使用前i种方法做出j个菜的方案数 
int C[101][2001],sum[101],ans,n,m,mod=998244353;
void read(int &x)
{
	x=(int)0;int ju=(int)1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')ju=-1;c=getchar();}
	while(c<='9'&&c>='0'){x=(int)(x*(int)10)+(int)(c-'0');c=getchar();}
	x*=ju;
	return;
}
int LINYIN()
{
	freopen("2019meal.in","r",stdin);
	freopen("2019meal.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			read(C[i][j]); 
			//scanf("%lld",&C[i][j]);
			sum[i]+=C[i][j];
			sum[i]=(sum[i]+mod)%mod;
		}
	}
	for(int X=1;X<=m;X++)
	{
		memset(dp1,0,sizeof(dp1));
		dp1[0][0+100]=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=-i+100;j<=i+100;j++)
			{
				dp1[i][j]=dp1[i-1][j];
				dp1[i][j]+=(dp1[i-1][j-1]*C[i][X]+mod)%mod;
				dp1[i][j]+=(dp1[i-1][j+1]*(sum[i]-C[i][X])+mod)%mod;
				dp1[i][j]=(dp1[i][j]+mod)%mod;
			}
		}
		for(int j=1;j<=n;j++)
		{
			ans-=(dp1[n][j+100]+mod)%mod;
			ans=(ans+mod)%mod;
		}
	}
	dp2[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			dp2[i][j]=dp2[i-1][j];
			for(int k=1;k<=m;k++)
			{
				dp2[i][j]+=(dp2[i-1][j-1]*C[i][k]+mod)%mod;
				dp2[i][j]=(dp2[i][j]+mod)%mod;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans+=dp2[n][i];
		ans=(ans+mod)%mod;
	}
	printf("%lld",ans); 
	return 0;
}
int LWH=LINYIN();
signed main()
{
	;
}