Cnoi2020 四角链の题解

前面的唐性质自己想
阅读题意可得，格子的编号为 \(1,2,3,…,n\) ，数字的集合为 \({1,2,…,n-1}\)
在合法方案中，有 \(k\) 个格子填了数，所以有 \(k\) 个数字被使用，那么一共有 \((n-1)-k\) 个数字没有用
把 \(k\) 个数和 \(k\) 个字符一一对应，每个数字 \(x\) 必须放在 \(\ge x\) 的格子上
但数字放在格子上后，格子本身没有额外的区分
换个角度看：
设 \(k\) 个被选的数字集合为 \(D\) ，每个数字 \(d\) 放在格子 \(f(d)\) 且 \(f\) 是单射到 被选中的格子集合 \(G\)
我们观察格子编号 \(\ge\) 数字的条件。
假设所有格子都可用，即为任意一个数字 \(d\) 可以选 \(d,d+1,d+2,…,n\) 中任意格子
这等价于分配问题，即为将数字 \(1,2,3,…,n-1\) 分配到 \(n-k\) 个块内
这里大神Mr_RedStone已经想到是第二类斯特林数了，可是为了向我一样的蒟蒻，我们还是一步步证明
我们增设一个数字 \(n\) 和一个格子 \(n\) ，并令虚拟数字只能放进虚拟格子
这个问题是典型的计数题目中的 \(rook polynomials\) 类的题目
根据结论，答案数为 \(S(n,k)\)
代码
[code]#include#define Code using#define by namespace#define jhc stdCode by jhc;#define int long longint in(){        int k=0,f=1;char c=getchar();        while(c'9'){if(c=='-')f=-1;c=getchar();}        while(c>='0'&&c