自动搬运

查看原文

来自洛谷，原作者为

	bzy 魔法みたいな算法で☆世界を変えるよ

搬运于2025-08-24 22:18:04，当前版本为作者最后更新于2020-07-09 01:03:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[Cnoi2020]四角链 官方拾遗

Subtask1( 20% ) : $n,k \le 10$ | 暴力枚举 or 打表

直接枚举每个格子填不填数以及填的数字是什么，理论计算次数小于 $10!=3628800$，可以轻松通过。

Subtask1,2( 60% ) : $n,k \le 1000$ | 动态规划

详情见其它题解。

Subtask1,2,3( 100% ) : $n,k \le 10^6$ | 斯特林数 + 容斥原理

做法见其它题解，这里补充答案是 ${n \brace n-k}$ 的正确证明姿势。

我们以这种填数方案为例:

然后我们加入 $0$ 号格子，并将所有数字减一 :

然后每个格子向自己数字对应的格子连边，容易证明形成的图是一个链森林。

上表生成的链森林为 $\{5\rightarrow3\rightarrow0\},\{4\},\{2\rightarrow1\}$。

可以发现一种链森林对应一种集合划分，链数等于 $n-k$, 所以答案是 ${n \brace n-k}$