ABC214G - Three Permutations 题解 这题做了一万年，最后也算是想出了一个比较强大的模型转换。。。 给定两个大小为 $N$ 的排列 $P,Q$ ，询问满足以下条件的排列 $R$ 的数量： 对于任意 $i\in [1, N]$ 均满足 $R_i\neq P_i \cap R_i\neq Q_i$ 。 $N\leq 3000$…

题目来源：ACL Beginner Contest F - Heights and Pairs。 给定一个大小为 $2N$ 的数组 $H$ ，要求将 $H$ 中的元素两两匹配，使得恰好构成 $N$ 个数对 $(H_i,H_j)$ 满足 $H_i\neq H_j$ 。 $N\leq 50000, H_i\leq 100000$ 。 首先容易想到通过容…

小球盒子模型总结 题目链接：洛谷十二重计数法。 设有 $n$ 个球，$k$ 个盒子： 球之间互不相同，盒子之间互不相同，可以空盒 根据乘法原理，答案就是 $k^n$ 。 球之间互不相同，盒子之间互不相同，每个盒子至多装一个球 相当于每个球找一个没有被选过的盒子放进去，答案是 $k^{\underline{n}}$ ，即 $k(k-1)\cdots(…

2021暑假训练组合数学题解 十二重计数法 小球盒子模型大合集 小球盒子模型总结。 「SDOI2016」排列计数 错位排列签到题 求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i = i$ 。 显然就是 $\binom{n}{m}D_{n-m}$ ，$D_i$ 表示 $i$ 的错位排列数量。 C…