解题报告-论对“阶乘计数”的新理解

这道题是我至今为止为一一道从开始到结束自己想出来的计数蓝题。其实性质很简单，把整个序列看成一个二叉小根堆，然后树形 \(\text{DP}\)，在一个子树中，必然是根是最小的，考虑给左子树分配哪些数，右子树分配哪些数，然后 \(ans_{rt}=ans_{ls}\times ans_{rs}\times C_{siz_{ls}+siz_{rs}}^{siz_{ls}}\) 即可。直到这里，我还认为它是一道值得推荐的好题，思维难度上把序列立起来变成了堆，后面还用了树形 \(\text{DP}\)；我从开始到想完一共用了一个多小时。

但是后面就逐渐恶心起来了。当年 \(\text{ZJOI}\) 设立模数 \(m\) 是反打表的，但是这里的模数却是真正有卡解法的作用的。正常而言，当我们计算 \(C_{2}^{2}\) 的时候，我们会用 \(\frac{2!}{2!\times (2-2)!}\) 这个算式，最后得到答案 \(1\)，其中下面的部分可以用快速幂求逆元。但是当模数 \(mod=2\) 的时候，\(2!\mod 2=0\)，所以这个算式求出来是 \(0\)。那这个时候怎么办呢？

这把我逼着去学了 \(\text{Lucas}\) 定理。其内容是 \(C_{m}^{n}=C_{\lfloor \frac{m}{mod}\rfloor}^{\lfloor \frac{n}{mod}\rfloor}\times C_{m\mod mod}^{n\mod mod}\)。也就是说，无论要计算的组合数有多大，我们都可以把其表示为一堆 \(C_j^i\) 相乘的形式，其中 \(i<mod,j<mod\)。

以前我们认为 \(\text{Lucas}\) 的实际意义是降低阶乘的计算复杂度，在这里其又衍生了一种新的情况：防止出现因 \(mod\) 过小而导致 \(\texttt{\color{Red}Wrong Answer}\) 的情况。

总结下来，这道题有以下两个好处：

• 锻炼思维。这确实是一个思维既不明显又不毒瘤的好题，但这不是很重点。
• 学会 \(\text{Lucas}\) 定理，和了解其新用法。以后在做 \(mod\) 不定的题的时候，除非有 \(mod>10^8\) 之类的限定，一定要用 \(\text{Lucas}\) 定理求方案数！