P16608 [SYSUCPC 2025] Larger or Smaller 题解

不难吧，不到 20min 就做完了，强烈谴责旁边的 @O_v_O 一开始不相信我的做法是对的。

首先可以直接把 的位置去掉并钦定 ，输出答案的时候乘上一个 即可。于是容易设出 表示填了 ，其中有 个位置满足 的方案数，有 。考虑转移，初始令 ，发现我们可以选择一个位置 并交换 与 的值。讨论 与 的大小关系：

• ：交换后有 ，有 种方案且 ，因此 。
• ：我们钦定了 ，因此这种情况无法直接转移。考虑错排问题的做法，假设现在只有 个数，接下来插入 与 ，那么 有 种可能。交换后有 ，有 ，因此 。
• ：交换后有 ，有 种方案且 ，因此 。

因此转移方程是：

时间复杂度 ，做完了。

void solve() {
	cin >> n >> mod;
	rep(i, 0, n) {
		C[i][0] = 1;
		rep(j, 1, i) {
			M(C[i][j] = C[i - 1][j - 1] + C[i - 1][j]);
		}
	}
	dp[0][0] = 1;
	rep(i, 1, n) {
		rep(j, 0, i) {
			dp[i][j] = 1ll * j * dp[i - 1][j] % mod;
			if(i > 1) M(dp[i][j] += 1ll * (i - 1) * dp[i - 2][j - 1] % mod);
			if(j) M(dp[i][j] += 1ll * (i - j) * dp[i - 1][j - 1] % mod);
		}
	}
	rep(i, 1, n) rep(j, 1, n - i) {
		cout << 1ll * C[n][i + j] * dp[i + j][i] % mod << " \n"[j == n - i];
	}
	return;
}