计数杂题选做（1）

一眼第二类斯特林数。

递推式 $C_n^k=C_{n-1}^{k-1}+k\times C_{n-1}^k$。考虑前 $n-1$ 个球放好，现在放第 $n$ 个球，是新放一个盒子还是放原来盒子。这种思路在许多组合排列相关的题中能用到，下一题就是例子。

注意此题盒子也是不相同的，还要再乘 $r$ 的阶乘。

记 $f_{i,j}$ 表示 $1$ 到 $i$ 的排列，小于号数为 $j$ 的方案数。

仍然考虑递推，假设加入了第 $i$ 个数，它比原来的数都大。分类讨论它插在最前面、最后面、两数中间且原来符号为小于号、大于号。会发现小于号数量只会不变或加 $1$。然后就得到 $f_{i,j}=f_{i-1,j-1}\times (i-j)+f_{i-1,j}\times (j+1)$。

观察下标的关系，会发现实际就是求以 $1$ 为根的小根堆个数，这样的计数也很经典。考虑计算 $f_i$，表示有 $i$ 个节点的小根堆个数，容易发现只要确定左儿子数量 $l$，那么就可以算出 $f_i$=$C_{i-1}^l\times f_l\times f_r$。表示除去根外的剩下节点中选一部分当左儿子，剩下为右儿子。而左右儿子互不影响，乘法原理。

注意这道题组合数的求解要用 Lucas 定理。

这道题和上一道题有些相似。

维护树根用并查集就行了，记录一个树根的 $sz$。

再考虑合并，将 $x$ 并到 $y$，令 $f_y\leftarrow f_y\times f_x\times C_{s{z}_y-1}^{s{z}_x}$，原理与上题一样。

考虑 dp，发现求非回文串很难求，正难则反，发现求回文串的话就简易许多了。

总数量为 $n!$，对于回文串，我们只考虑左右中一侧，设每个字符出现次数 $cn{t}_i$ 为偶数，那么我们在一侧必要放 $\frac{cn{t}_i}{2}$ 个，由于字符有下标关系，所以用排列，放字符数为 $A_{cn{t}_i}^{\frac{cn{t}_i}{2}}$，然后 $\frac{n}{2}$ 个位置，也可以任意排列，所以最终答案为 $n!-\frac{n}{2}!\times A_{cn{t}_i}^{\frac{cn{t}_i}{2}}$。

$2^n$ 个集合，肯定不能全部枚举，对于这种很常见的解决方法时考虑一个元素加入对全部方案的贡献。

我们先将线段按左端点从小到大排序，记 $f_i$ 为前 $i$ 条线段的总方案数。对于新的一条线段，不加入则为 $f_{i-1}$，加入了，之前与它相交的方案数仍为 $f_{i-1}$，若不与它相交，设数量为 $j$，则会产生 $2^j\times 1$ 的贡献。

最后转移方程就出来了。$j$ 可以考虑前缀和计算，反正数据范围也不大。