Campinatorics

Chasing_Meteors · 2025-12-04 14:56:20 · 题解

有五个元素，行、列、1、2、3。

先从 3 开始考虑，因为 3 直接被限定了数量，考虑枚举放了 k 个 3，则此时我们要将 k 个 3 放入 n\times n 的网格中，每一行和每一列都只能有至多一个 3，此时我们先考虑行（行和列本质相同），选出来哪些行被覆盖，方案数是 \binom{n}{k}，接着放入 3，由于不能重复，方案数是 A_n^k。

接着考虑 2 和 1，不难发现他们没有本质区别，都是每一行和每一列之多出现一次，两种思路，要么同时枚举，要么先枚举其中一个。同时枚举的话限制不好处理。

于是不妨先枚举 1，原先的 k 个 3 占据了 k 行，剩余 n-k 行，我们要放入 n-k 个 1，并选择每一行的 1 所在的列，方案数是 (n-k)!，接着考虑 2，我们同样是有 n-k 个行要放入，每个行有一个位置被占据，不能放入，写成形式化一点的：求一个排列 A 满足 A_i\ne B_i，这个是经典错排，于是就做完了。