[CSP-S2 2019]Emiya 家今天的饭 题解

题目地址：洛谷：P5664 Emiya 家今天的饭 – 洛谷 | 计算机科学教育新生态

题目描述

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 总共会做 $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} a_{i,j}$​ 道不同的菜。

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

• Emiya 不会让大家饿肚子，所以将做至少一道菜，即 $k \geq 1$​
• Rin 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同
• Yazid 不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即 $​\lfloor \frac{k}{2} \rfloor$​ 道菜）中被使用
  • 这里的 $​\lfloor x \rfloor$​ 为下取整函数，表示不超过 $​x$​ 的最大整数。

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

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

题意简述

一共有 $n$ 种烹饪方法和 $m$ 种主要食材，一道菜仅对应一种烹饪方法和一种主要食材。使用第 $i$ 种烹饪方法和第 $j$ 种主要食材，Emiya 可以做出 $a_{i,j}$ 道不同的菜。

求满足以下条件的菜的集合数：

• 非空；
• 每道菜的烹饪方法互不相同；
• 集合中每种主要食材的菜数不超过集合大小的一半（向下取整）。

输入输出格式

输入格式：

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

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

输出格式：

仅一行一个整数，表示所求方案数对 $998,244,353$ 取模的结果。

输入输出样例

样例 #1

输入样例#1：

2 3
1 0 1
0 1 1

输出样例#1：

3

样例 #2

输入样例#2：

3 3
1 2 3
4 5 0
6 0 0

输出样例#2：

190

样例 #3

输入样例#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

输出样例#3：

742

数据范围

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

题解

参考资料：题解 P5664 【Emiya 家今天的饭【民间数据】】 – Caro23333 的博客 – 洛谷博客

居然在 NOIP 级别的比赛中见到了计数 DP，很难想象以后的 NOIP 对于数学知识的考察会变成什么样。那个只有一道很水的数论/组合签到题的时代已经结束了。

首先本题是组合数学/计数类型的问题，这类题通常有两种解决方式：推公式或 DP，本题中可以采用 DP 求解。

接下来考虑如何设计 DP 状态。如果正面解决，就必须对每种主要食材的出现次数做小于集合大小的一半的限制，这需要记录下每种主要食材的出现次数，不是很可行。因此可以采用正难则反的策略，容易发现不合法的情况中只会有一种主要食材超过集合大小的一半，处理这个限制仅需记下一种主要食材的出现次数，问题变得简单了。

所有方案数

首先从一个较好解决的问题入手，由于答案=所有方案数-不合法方案数，我们需要知道所有的方案有多少种。

定义 $g(i, j)$ 表示前 $i$ 种烹饪方式中，每种最多选出一道菜的情况下，当前集合中有 $j$ 道菜的方案数，则决策为当前处理的第 $i$ 种烹饪方式是否选出一道菜，记 $s(i)$ 代表第 $i$ 种烹饪方式一共可做出的菜数，即 $s(i) = \sum\limits_{j=1}^m a_{i, j}$ 转移方程如下：

$$ g(i,j) = \underset{不选}{g(i-1, j)} + \underset{从 s(i) 道菜中选 1 种}{g(i-1,j-1) \cdot s(i)} $$

初始值为 $g(0, 0)=1$（什么都没做，有 $1$ 种方案），所有的方案数为 $\sum\limits_{i=1}^n g(n, i)$，由于集合不能为空，$g(n, 0)$ 的值不能加入方案数中。

这一部分的复杂度为 $O(n^2)$。

不合法方案数

由于不合法的方案中，只有一种主要食材的数量会超过集合大小的一半，可以枚举超限的主要食材，而只记录下其他食材的数量之和，不分开记录。

定义 $f(in, j, k)$ 表示考虑前 $in$ 种烹饪方式，当前要超限的主要食材的出现次数为 $j$，其他主要食材的出现次数之和为 $k$。决策有三种：当前考虑的第 $in$ 种烹饪方式不选、选要超限的那种主要食材的菜或选其他主要食材的菜，记 $s(i)$ 代表第 $i$ 种烹饪方式一共可做出的菜数，且当前要超限的主要食材编号为 $im$，有转移方程：

$$ f(in, j, k) = \underset{不选}{f(in-1, j, k)} + \underset{选要超限的主要食材}{f(in-1, j-1,k) \cdot a_{in, im}} + \underset{选其他的主要食材}{f(in-1,j,k-1) \cdot [s(in)-a_{in,im}]} $$

将上述 DP 在以每一种主要食材为超限食材的情况下都计算一遍，对于 $im$ 这种食材为超限食材的情况，不合法的方案数为 $\sum\limits_{k < j} f(n, j, k)$。将这些不合法的方案数加起来就获得了总的不合法方案数了。但这种方式的复杂度是 $O(n^3m)$ 的，无法通过本题。

考虑优化上述方法，将不合法的方案满足的条件 $k < j$ 移项，得到表达式 $j-k > 0$，其实判断一个方案是否合法，仅需要判断 $j-k$ 的符号即可，我们考虑将之前状态中的 $j$ 和 $k$ 两个维度变为一维 $j-k$ 的值，这将会减少一层循环，使复杂度降至 $O(n^2m)$。

接下来考虑上面的改变会对转移方程造成什么样的影响，事实上，仅需将方程中的两维改为一维即可：

$$ f(in, j) = \underset{不选}{f(in-1, j)} + \underset{选要超限的主要食材}{f(in-1, j-1) \cdot a_{in, im}} + \underset{选其他的主要食材}{f(in-1,j+1) \cdot [s(in)-a_{in,im}]} $$

由于 $j-k$ 的值可以为负数，而数组下标不能为负数，因此下标应当处理为 $j-k+n$，以让下标的值非负。DP 的初始值为 $f(0, 0)=1$（什么都没做，其中第二维下标应处理为 $n$），对于每一种超限食材的情况，不合法的方案数为$\sum\limits_{j=1}^n f(n, j)$（第二维下标应处理为 $j + n$）。

最后，将所有方案数减去不合法方案数就得到了最终答案，总复杂度为 $O(n^2m)$。

代码

// Code by KSkun, 2019/12
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <utility>

typedef long long LL;
typedef std::pair<int, int> PII;

inline char fgc() {
	static char buf[100000], * p1 = buf, * p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
		? EOF : *p1++;
}

inline LL readint() {
	LL res = 0, neg = 1; char c = fgc();
	for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
	for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
	return res * neg;
}

inline char readsingle() {
	char c;
	while(!isgraph(c = fgc())) {}
	return c;
}

const int MAXN = 105, MAXM = 2005;
const int MO = 998244353;

int n, m;
LL a[MAXN][MAXM], s[MAXN], f[MAXN][MAXN << 1], g[MAXN][MAXN];

inline LL A(int in, int im) { // 让方程不那么长的简化
	return (s[in] - a[in][im] + MO) % MO;
}

int main() {
	n = readint(); m = readint();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			a[i][j] = readint();
			s[i] = (s[i] + a[i][j]) % MO;
		}
	}

	LL sum1 = 0, sum2 = 0;
	for (int im = 1; im <= m; im++) {
		memset(f, 0, sizeof(f));
		f[0][n] = 1;
		for (int in = 1; in <= n; in++) {
			for (int j = n - in; j <= n + in; j++) {
				f[in][j] = (f[in - 1][j] + f[in - 1][j - 1] * a[in][im] % MO + f[in - 1][j + 1] * A(in, im) % MO) % MO;
			}
		}
		for (int i = 1; i <= n; i++) {
			sum1 = (sum1 + f[n][n + i]) % MO;
		}
	}
	g[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			g[i][j] = g[i - 1][j];
			if (j > 0) g[i][j] = (g[i][j] + g[i - 1][j - 1] * s[i] % MO) % MO;
		}
	}
	for (int i = 1; i <= n; i++) {
		sum2 = (sum2 + g[n][i]) % MO;
 	}
	printf("%lld", (sum2 - sum1 + MO) % MO);
	return 0;
}