Description
(Emiya)是个擅长做菜的高中生，他共掌握(n)种烹饪方法，且会使用(m)种主要食材做菜。为了方便叙述，我们对烹饪方法从(1 sim n)编号，对主要食材从(1 sim m)编号。
(Emiya)做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，(Emiya)会做(a_{i,j})道不同的使用烹饪方法(i)和主要食材(j)的菜（(1 leq i leq n, 1 leq j leq m)），这也意味着(Emiya)总共会做(sumlimits_{i=1}^{n} sumlimits_{j=1}^{m} a_{i,j})道不同的菜。
(Emiya)今天要准备一桌饭招待(Yazid)和(Rin)这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含(k)道菜的搭配方案而言：
- (Emiya)不会让大家饿肚子，所以将做至少一道菜，即(k geq 1)
- (Rin)希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同
- (Yazid)不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即(lfloor frac{k}{2} floor)道菜）中被使用
这里的(lfloor x floor)为下取整函数，表示不超过(x)的最大整数。
这些要求难不倒(Emiya)，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。
(Emiya)找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数(998,244,353)取模的结果。
Input
第(1)行两个用单个空格隔开的整数(n,m)。
第(2)行至第(n + 1)行，每行(m)个用单个空格隔开的整数，其中第(i + 1)行的(m)个数依次为(a_{i,1}, a_{i,2}, cdots, a_{i,m})。
Output
仅一行一个整数，表示所求方案数对(998,244,353)取模的结果
Sample Input1
2 3
1 0 1
0 1 1
Sample Output1
3
(PS):
由于在这个样例中，对于每组(i, j)，(Emiya)都最多只会做一道菜，因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。
符合要求的方案包括：
- 做一道用烹饪方法(1)、主要食材(1)的菜和一道用烹饪方法(2)、主要食材(2)的菜
- 做一道用烹饪方法(1)、主要食材(1)的菜和一道用烹饪方法(2)、主要食材(3)的菜
- 做一道用烹饪方法(1)、主要食材(3)的菜和一道用烹饪方法(2)、主要食材(2)的菜
因此输出结果为(3 mod 998,244,353 = 3)。 需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足(Yazid)的要求。
Sample Input2
3 3
1 2 3
4 5 0
6 0 0
Sample Output2
190
(PS):
(Emiya)必须至少做(2)道菜。
做(2)道菜的符合要求的方案数为(100)。
做(3)道菜的符合要求的方案数为(90)。
因此符合要求的方案数为(100 + 90 = 190)。
Sample Input3
5 5
1 0 0 1 1
0 1 0 1 0
1 1 1 1 0
1 0 1 0 1
0 1 1 0 1
Sample Output3
742
Hint
对于所有测试点，保证(1 leq n leq 100)，(1 leq m leq 2000)，(0 leq a_{i,j} lt 998,244,353)。
题解
(32pts)：(DFS)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
const int MOD=998244353;
const int N=150,M=2500;
int n,m,a[N][M],l[M];//l[]记录每一列选了多少个
typedef long long ll;
ll Ans;
void Dfs(int id,int _n,ll _c,int Max)
{//当前枚举到第id行，选了_n个，方案数为_c，选的最多的列的所选个数为Max
if(id>n) return;
if(Max>n/2) return;//不符合要求
Dfs(id+1,_n,_c,Max);
int t1,t2; ll t3;
for(int i=1;i<=m;++i)
if(a[id][i])
{
++l[i],
t1=_n+1,//选
t2=max(Max,l[i]),//选
t3=_c*a[id][i]%MOD;//选
if(t2<=(t1/2)) Ans=(Ans+t3)%MOD;//符合要求
Dfs(id+1,t1,t3,t2);
--l[i];//回溯
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) scanf("%d",&a[i][j]);
Dfs(1,0,1,0),
cout<<Ans<<endl;
return 0;
}
(100pts)：(DP)
下面的方法来自题解【luogu5664 Emiya 家今天的饭】
先把总数符合每道菜的烹饪方法互不相同的总方案求出来，再用(DP)求出不符合每种主要食材至多在一半的菜的方案数，最后求差即可
(DP)求出不符合每种主要食材至多在一半的菜的方案数如下：
考虑我们需要的限制条件(k>left lfloor frac{j}{2} ight floor)，变形一下可以得到(2k+n-j>n)。观察这个式子，可以发现，(n-j)就是这(n)行里没有选的行数。然后一个奇妙的想法就出来了，对于每个节点，选它时当做该列选了两次，而对于某一行不选时，当做所有列选了一次，最终要找的就是当前列被选超过(n)次的方案。
就得到了如下的状态转移方程
f[j][k]=(f[j][k]+f[j-1][k]*(cnt[j]-w[j][i]))%P;//不选当前列
f[j][k+1]=(f[j][k+1]+f[j-1][k])%P;//不选当前行
f[j][k+2]=(f[j][k+2]+f[j-1][k]*w[j][i])%P;//选当前行当前列对应的节点
(My Code)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
const int N=250,M=2000;
int n,n2,m;
ll a[N][M],sa[N],Ans,f[N][N];
void Read()
{
Ans=1;
scanf("%d%d",&n,&m);
n2=n<<1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
cin>>a[i][j];
sa[i]=(sa[i]+a[i][j])%MOD;
}
Ans=(Ans*(sa[i]+1))%MOD;//计算全部答案,注意不选也是一种情况
}
Ans=(Ans-1+MOD)%MOD;//减去全部不选的情况
}
void DP()
{
for(int i=1;i<=m;++i)
{
for(int j=0;j<=n2;++j)
for(int k=0;k<=n2;++k) f[j][k]=0;
f[0][0]=1;//DP初值
for(int j=1,YH=0;j<=n;++j,YH+=2)
for(int k=0;k<=YH;++k)
{
f[j][k]=(f[j][k]+f[j-1][k]*(sa[j]-a[j][i]+MOD)%MOD)%MOD,
f[j][k+1]=(f[j][k+1]+f[j-1][k])%MOD,
f[j][k+2]=(f[j][k+2]+f[j-1][k]*a[j][i]%MOD)%MOD;
}
for(int j=n+1;j<=n2;++j)
Ans=(Ans-f[n][j]+MOD)%MOD;//减去当前枚举到的不合法方案
}
}
int main()
{
Read(),DP(),cout<<Ans<<endl;
return 0;
}