题解 P6162 【[Cnoi2020]四角链】

· · 题解

[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} 的正确证明姿势。

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

编号 1 2 3 4 5
数字 2 1 4

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

编号 0 1 2 3 4 5
数字 1 0 3

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

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

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