題目傳送門

洛谷 P5664

前言

本題解為作者整合了自己學習其他題解后為自己寫的用以復習的筆記，不喜勿噴謝謝，但是有邏輯錯誤或語言不清晰之處歡迎提出！

題目描述

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\) 道菜）中被使用

這些要求難不倒 Emiya，但他想知道共有多少種不同的符合要求的搭配方案。兩種方案不同，當且僅當存在至少一道菜在一種方案中出現，而不在另一種方案中出現。

Emiya 找到了你，請你幫他計算，你只需要告訴他符合所有要求的搭配方案數對質數 \(998,244,353\) 取模的結果。
這里的 \(\lfloor x \rfloor\) 為下取整函數，表示不超過 \(x\) 的最大整數。

題意簡化

給定一個 \(n\) 行 \(m\) 列的矩陣 \(a\) ，每行 \(i\) 中至多選擇某一列 \(j\) 的 \(a_{i,j}\) 種可能中的1個，求有多少種方案滿足以下3個約束。

1. 至少選擇一個
2. 每行至多選一個
3. 每列最多選總數的一半

思路

直接計數dp。目標時間復雜度： \(\text O(mn^2)\)
注意到約束3過于討嫌難以處理，所以 正難則反 ，考慮容斥原理：
對于約束3，若違反，則說明此列中有超過一半的菜，所以其他列肯定是少于一半，符合要求的。
既然如此，我們就枚舉是哪一列違反了約束3，統計這些不合法方案總數，最后用總方案數減去即得答案。

統計總方案數

具體的，令 \(tot[i][j]\) 表示前 \(i\) 行中，選擇了 \(j\) 次的方案數，注意 \(j\) 次等價于選了 \(j\) 行，因為每行只能選一個。
則轉移方程考慮兩種情況：

1. 這一行沒選
2. 這一行選了某一個菜

故有：

，其中 \(s[i]\) 表示第 \(i\) 行中的總菜數，即

統計非法方案

對于第 \(col\) 列，令 \(dp[i][j][k]\) 代表前 \(i\) 行中選了 \(j\) 個 \(col\) 的菜品，選了 \(k\) 個其他菜的菜品。
則考慮三種情況：

1. 這一行啥都沒選
2. 這一行選了 \(col\) ，總共有 \(a[i][col]\) 種可能選擇，乘法原理
3. 這一行沒選 \(col\) 但選了其他的，總共有 \(s[i]-a[i][col]\) 種可能選擇，同樣乘法原理開大懟上去

于是有：

優化

這個優化比較玄學，也是我寫這篇題解的主要搞懂對象。
注意到非法方案滿足 \(j>k\) ，即 \(j-k>0\)
換言之，我們只需維護 \(j-k\) ，不需要真正關注 \(j,k\) 的值。
那么，令 \(dp[i][\triangle x]\) 代表前 \(i\) 行中，選了菜品 \(col\) 的減去選了菜品 \(col\) 之外的值為 \(\triangle x\) 的方案數。
轉移方程需考慮三種情況：

1. 這一行啥都沒選，直接繼承 \(dp[i-1][\triangle x]\)
2. 這一行選了 \(col\) ，\(\triangle x\) 加 \(1\)
3. 這一行選了 \(col\) 之外的， \(\triangle x\) 減 \(1\)

如何證明這囊括了所有情況，不重不漏呢？
這個我也不會，如果有知道的麻煩在評論區不吝賜教，謝謝！

總之，新的轉移方程挺顯然的（用 \(j\) 代替 \(△x\)）：

最后，注意到 \(dp[i][j]\) 中的 \(-n\leq j\leq n\) ，所以給 \(dp[i][j]\) 的 \(j\) 強行都加 \(n\) ，
那么最后符合非法方案的就從 \(j>0\) 變成 \(j>n\) ，即最后減方案數減的是

AC 代碼：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 998244353;
const int N = 105, A = 2005;
int n, m;
ll a[N][A], s[N];
// tot[i][j]: 前i種烹飪方法中選了j個食材的總方案數
ll tot[N][N];
// dp[i][j+n]: 前i種烹飪方法中超限的食材出現次數減去其他食材出現次數為j的非法方案數
ll dp[N][N * 2];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
			(s[i] += a[i][j]) %= M;
		}
		// printf("There are %lld ways to cook with way %d\n", s[i], i);
	}
	tot[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		tot[i][0] = tot[i - 1][0];
		for (int j = 1; j <= n; ++j) {
			tot[i][j] = tot[i - 1][j] + tot[i - 1][j - 1] * s[i] % M;
			tot[i][j] %= M;
			// printf("There's %lld ways to pick %d columns from the first %d rows.\n", tot[i][j], i, j);
		}
	}

	// printf("tot:\n");
	// for (int i = 1; i <= n; ++i) {
	// 	for (int j = 0; j <= n; ++j) {
	// 		printf("%lld\t", tot[i][j]);
	// 	}
	// 	printf("\n");
	// }

	ll ans = 0;
	for (int col = 1; col <= m; ++col) {
		// printf("If %d is the invalid ingredient:\n", col);
		memset(dp, 0, sizeof(dp));
		dp[0][n] = 1;
		for (int i = 1; i <= n; ++i) {
			for (int j = n - i; j <= n + i; ++j) {
				dp[i][j] = dp[i - 1][j];
				(dp[i][j] += dp[i - 1][j - 1] * a[i][col] % M) %= M;
				(dp[i][j] += dp[i - 1][j + 1] * (s[i] - a[i][col]) % M) %= M;
				// for (int k = 1; k <= m; ++k) {
				// 	dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k] * a[i][j] + dp[i - 1][j][k - 1] * (s[i] - a[i][j]);
				// }
			}
		}
		// printf("DP:\n");
		// for (int i = 1; i <= n; ++i) {
		// 	for (int j = n - i; j <= n + i; ++j) {
		// 		printf("dp[%d][%d]: %lld\t", i, j - n, dp[i][j]);
		// 	}
		// 	printf("\n");
		// }
		for (int i = 1; i <= n; ++i)
			(ans -= dp[n][i + n]) %= M;
		ans = (ans % M + M) % M;
	}
	for (int i = 1; i <= n; ++i) {
		(ans += tot[n][i]) %= M;
	}
	cout << ans << '\n';
	return 0;
}

后記

這里其實可以滾一下，把dp第一維壓到2，用奇偶滾一下的說但是沒必要
證明差分dp可行目前我能想到的只有暴力打印每次迭代的dp數組去看是不是滿足j-k為定值的都相等/加起來怎么怎么樣的，有知道具體方法的務必留一下，謝謝！