题解 P5598 【【XR-4】混乱度】

Rainy_chen · 2019-10-22 07:11:05 · 题解

题面

给出n种颜色的球，每种颜色的球没有区别，定义f(l,r)为颜色为l到r的所有球的不同排列数，求\sum_{l=1}^n\sum_{r=1}^n(f(l,r)\mod p)。

吐槽

考场上想出了题解的第一步，果然我已经从「完全没有计数基础」进化到了「有一定组合数学基础」了吗233。

然后感谢XR团队提供的优质题目/亲亲。

题解

我们考虑f(l,r)该怎么计算，实际上应该是一个\binom{\sum_{i=l}^ra_i}{a_l}\times f(l+1,r)，理解方式大概就是在长度为\sum_{i=l^r}a_i的序列中选出a_i个位置设置成颜色l，然后剩下的位置的方案数恰好就是f(l+1,r)。从同样的角度理解你还可以发现f(l,r)=\binom{\sum_{i=l}^ra_i}{a_r}\times f(l,r-1)。
当然，对于f(l,l)，其值为1。

我们令S(l,r)表示\sum_{i=l}^ra_i，之后我们展开f(l,r)，应该可以得到

以上是题解的第一步

之后我们考虑Lucas定理，Lucas定理一般表示为\binom nm\mod p=\binom{n/p}{m/p}\binom{n\mod p}{m\mod p}\mod p，其中，a/b表示\left\lfloor\frac ab\right\rfloor。

实际上如果我们将n,m看做两个p进制数\overline{n_a..n_2n_1n_0},\overline{m_b..m_2m_1m_0}的话，\binom nm\mod p就是\prod_{i=0}^{max(a,b)}\binom{n_i}{m_i}\mod p。

有一个并不显然的结论，若\binom {n+m}m\mod p为0，那么这代表着在p进制下计算n+m时有一位发生了进位。

一个比较感性的理解方式是若\binom{n+m}m\mod p=0，那么n+m的p进制上必然有一位是小于m的p进制上的这一位的，而发生这个情况的唯一可能性是这一位加了一个数产生了进位。

或许你还会考虑到这一位可能被其他位置的进位所影响，所以我们这里找的是产生进位的最低位，如果存在进位则必然存在这一位，并且无论如何这一位都不会被其他位影响。

然后我们发现f(l,r)\mod p=0的条件就是\sum_{i=l}^ra_i在p进制下运算时出现了进位。
更优秀的性质是如果f(l,r)\mod p=0，那么f(l-1,r)=f(l,r+1)=0,因为这两者都可以从f(l,r)通过乘法计算而来。这意味着是否进位是满足单调性的。

于是我们得出了解法1，对每个点r求出最小的l使得f(l,r)不产生进位，之后暴力计算\sum_{i=l}^rf(i,r)。

第一部分的测试点中期望的不产生进位的区间个数是\theta(n)个左右，具体证明可以参考XR题解，这里不再赘述。

对于第二部分的测试点，a_i不再随机，这意味着可能会被人为构造出大量的0来使解法1的区间个数以及区间长度大量增长，这时复杂度完全取决于出题人是否良心。

于是你可以考虑消除0对于答案的影响，容易发现若a_l=0则f(l,r)=\binom{S(l,r)}{0}f(l+1,r)=f(l+1,r)，于是将所有0缩起来，只记录0出现的数量，之后在新的不包含0的序列上再沿用解法1即可。

至于说在不包含0的序列上用解法1的时间复杂度，容易发现区间长度不会超过(p-1)\lceil log_pa_i\rceil，主要每一个数至少在一位上至少为1，然后最多可以有(p-1)\lceil log_pa_i\rceil个1，只要再出现一个数就会产生进位。

于是最坏复杂度是O(nplog_p^2a_i)。

正解与第二部分的算法是十分相似的，在第二部分中计算组合数时使用了lucas定理，而lucas定理的本质是将数转化为p进制数后逐位计算。

所以我们可以在进行解法2之前先将每一个a_i拆分成p进制数。 然后进行解法2的扫描时，把p进制的每一位的值储存下来，对于扫到的数a_i，将其拆分后的p进制数在其几个非0位上将储存的值更新掉。