Solution - P2606 [ZJOI2010]排列计数

P2606 [ZJOI2010]排列计数

idea:

树形 $dp$ ，对于组合数的计算。

解决方案：

我的方法非常地奇怪，但运用了许多有亲和力的算法。

首先很容易发现所谓的数组是一棵有 $n$ 个节点的完全二叉树，要求父节点比子节点大。

我们设 $sz_i$ 表示以 $i$ 为根节点的子树大小， $f_i$ 表示以 $i$ 为根节点的子树内部分配 $sz_i$ 个不同的数的方案数。由于所有数都是不同的，所以 $f_i$ 并不会受到分配到的 $sz_i$ 个数的具体数值的影响。

显然地，当 $i>n$ 时， $sz_i = 0$ ；

当 $i<=n$ 时， $sz_i = sz_{2\cdot i} + sz_{2\cdot i + 1} +1$ 。

$f_i$ 的转移也是非常显然的：

$$f_i = f_{2\cdot i}\cdot f_{2\cdot i + 1} \cdot C_{i-1}^{sz_{2\cdot i}}$$

那么我们就可以 $O(n)$ 进行树形 $dp$ 了。

然而模数可以非常小，故不能直接逆元。

考虑先线性筛， $low_i$ 表示 $i$ 的最小质因子。令 $cnt_i$ 表示 $i$ 需要乘的次数（除为负数）。那么 $cnt_i$ 是可以通过树状数组区间修改单点查询维护的。最后在倒序从 $n$ 循环到 $2$ ，如果 $i$ 是合数，就将 $cnt_i$ 加到 $cnt_{low_i}$ 和 $cnt_{\frac{i}{low_i}}$ 上去；如果 $i$ 是质数，就计算。这样就可以 $O(n\log n)$ 计算答案了。

总的时间复杂度 $O(n\log n)$ ，空间 $O(n)$ 。

听说有个叫做 $Lucas$ 定理的东西，不知是什么意思。