题意描述

Emiya 是个擅长做菜的高中生，他共掌握 $n$ 种烹饪方法，且会使用 $m$ 种主要食材做菜。为了方便叙述，我们对烹饪方法从 $1 \sim n$ 编号，对主要食材从 $1 \sim m$ 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，Emiya 会做 $a_{i,j}$ 道不同的使用烹饪方法 $i$ 和主要食材 $j$ 的菜 $(1\le i\le n, 1\le j\le m)$ ，这也意味着 Emiya 总共会做菜的数目为：

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含 $k$ 道菜的搭配方案而言:

  • Emiya 不会让大家饿肚子，所以将做至少一道菜，即 $k \ge 1$

  • Rin 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同

  • Yazid 不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即 $\lfloor \frac k2 \rfloor$ 道菜）中被使用

    • 这里的 $\lfloor x\rfloor$ 为下取整函数，表示不超过 $x$ 的最大整数

这些要求难不倒 Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。

Emiya 找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数 $998,244,353$ 取模的结果。

输入格式

从文件 meal.in 中读入数据。

第 $1$ 行两个用单个空格隔开的整数 $n, m$。

第 $2$ 行至第 $n + 1$ 行，每行 $m$ 个用单个空格隔开的整数，其中第 $i + 1$ 行的 $m$ 个数依次为 $a{i,1}, a{i,2}, \dots, a_{i,m}$。

输出格式

输出到文件 meal.out 中。 仅一行一个整数，表示所求方案数对 $998,244,353$ 取模的结果。

Input & Output ‘s examples

Input ‘s eg 1

2 3
1 0 1
0 1 1

Output ‘s eg 1

3

样例解释 1

由于在这个样例中，对于每组 $i, j$，Emiya 都最多只会做一道菜，因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。

符合要求的方案包括：

  • 做一道用烹饪方法 $1$、主要食材 $1$ 的菜和一道用烹饪方法 $2$、主要食材 $2$ 的菜
  • 做一道用烹饪方法 $1$、主要食材 $1$ 的菜和一道用烹饪方法 $2$、主要食材 $3$ 的菜
  • 做一道用烹饪方法 $1$、主要食材 $3$ 的菜和一道用烹饪方法 $2$、主要食材 $2$ 的菜

因此输出结果为 $3 \bmod 998,244,353 = 3$。 需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足 Yazid 的要求。

Input ‘s eg 2

3 3
1 2 3
4 5 0
6 0 0

Output ‘s eg 2

190

样例解释 2

Emiya 必须至少做 $2$ 道菜。

做 $2$ 道菜的符合要求的方案数为 $100$。

做 $3$ 道菜的符合要求的方案数为 $90$。

因此符合要求的方案数为 $100 + 90 = 190$。

Input ‘s eg 3

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

Output ‘s eg 3

742

数据范围和约定

测试点编号 $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$ $1000$
$8$ $10 $ $3$ $1000$
$9\sim 12$ $40$ $2$ $1000$
$13\sim 16$ $40$ $3$ $1000$
$17\sim 21$ $40$ $500$ $1000$
$22\sim 25$ $100$ $2000$ $998,244,353$

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

分析

去年 Day2 考场上看 T1 是组合想都没想就写了个十来分的暴力扔了，现在发现仔细想想就有 64 分……

64pts

观察一下数据范围，不难发现测试点 $1$ 到 $16$ 的 $m \leq 3$ ，即最多只有三种食材。

那我们不妨设 $f[i][j][k][l]$ 表示对于前 $i$ 种烹饪方法，用食材一做 $j$ 道菜，食材二做 $k$ 道菜，食材三做 $l$ 道菜的方案数，之后大力 $\text{dp}$ 即可。

时间复杂度 $O(n^4)$。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;

ll n , m , a[50][50]; 
ll f[50][50][50][50];	//f[i][j][k][l] 对于前i种烹饪方式，选择j道食材1，k食材2，l食材3的2方案数目 


int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    read(n) , read(m);
    rep(i , 1 , n){
		rep(j , 1 , m){
			read(a[i][j]); 
		}
	}
	f[0][0][0][0] = 1;
	rep(i , 1 , n){
		rep(j , 0 , i){
			rep(k , 0 , i){
				rep(l , 0 , i){
					f[i][j][k][l] += f[i - 1][j][k][l] % HA , f[i][j][k][l] %= HA;
					if(j) f[i][j][k][l] += (f[i - 1][j - 1][k][l] * a[i][1]) % HA , f[i][j][k][l] %= HA;
					if(k) f[i][j][k][l] += (f[i - 1][j][k - 1][l] * a[i][2]) % HA , f[i][j][k][l] %= HA;
					if(l) f[i][j][k][l] += (f[i - 1][j][k][l - 1] * a[i][3]) % HA , f[i][j][k][l] %= HA;
				}
			}
		}
	}
	ll res = 0;
	rep(i , 0 , n / 2){
		rep(j , 0 , n / 2){
			rep(k , 0 , n / 2){
				ll lim = (i + j + k) / 2;
				if(i > lim || j > lim || k > lim) continue;
				res += f[n][i][j][k] , res %= HA;
			}
		}
	}
	printf("%lld\n" , (res - 1) % HA);

    return 0;
}

84pts

后面的测试点 $m$ 变的很大，已经难以直接维护合法的方案数目了。

正难则补，则我们维护不合法的方案数目，之后用总方案数减去即可。

考虑不合法方案的特点：不合法的方案会有且仅有一种食材的使用次数大于总菜数的一半，则我们考虑钦定一种食材作为这个食材，为了下文叙述方便，我们称其为主菜

设 $f[i][j][k]$ 表示对于前 $i$ 种烹饪方法，做了 $j$ 到菜，有 $k$ 到是主菜的方案数，$sum[i]$ 表示第 $i$ 种烹饪方法能够做出的总菜数，且前作为主菜的原料为 $l$ 。则有三种不同的决策，分别是第 $i$ 种烹饪方式不选，选它做主菜，选它做副菜，写成方程，就是：

其中，不合法的方案数为：

之后用总方案数减一下即可。

这样时间复杂度是 $O(m \times n^3)$ 的，无法通过本题，但可以拿到 $84$ 分的好成绩。

100pts

满分做法实际上是在 $84$ 分的基础上进行优化。

移一下项，则 $j < 2k$ 相当于 $2k - j > 0$。设 $j’ = 2k - j$，则我们只需要表示 $f[i][j’]$ 的结果即可。

但 $2k - j$ 可能是负数，因此我们需要数组平移。

时间复杂度 $O(m \times n^2)$，足以通过本题。

剩下的细节详见下方代码。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 100000 + 5;
const int HA = 998244353;

ll n , m , a[105][2005]; 

ll sum[105];
ll f[105][210];

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    read(n) , read(m);
    rep(i , 1 , n){
		rep(j , 1 , m){
			read(a[i][j]);
		}
	}
	ll cnt = 1;
	rep(i , 1 , n){
		rep(j , 1 , m){
			sum[i] += a[i][j] , sum[i] %= HA;
		}
		cnt *= (sum[i] + 1) % HA , cnt %= HA;
	}
	ll del = 0;
	const int CON = 105;
    rep(k , 1 , m){
    	clean(f , 0) , f[0][CON] = 1;
		rep(i , 1 , n){
			for(int j = CON - i; j <= CON + i; j ++){
				f[i][j] = f[i - 1][j] % HA;
				if(j) f[i][j] += f[i - 1][j - 1] * a[i][k] , f[i][j] %= HA;
				f[i][j] += f[i - 1][j + 1] * (sum[i] - a[i][k] + HA) % HA , f[i][j] %= HA;
			} 
		}
		for(int i = CON + 1; i <= 2 * CON; i ++) del += f[n][i] , del %= HA;
	}
	printf("%lld\n" , (cnt - del - 1 + HA) % HA);
    
    return 0;
}

THE END