本文共 381 字，大约阅读时间需要 1 分钟。

在这里记录一下看过的题目的思路，有时间写。

BZOJ1129: [POI2008]Per 从小到大依次考虑每种数字，按照这种数字在当前序列中的相对位置来计算这是第几类，每一类都会有剩下的所有数字的本质不同的排列个数得到。 那么考虑这是第几类，从前向后考虑每个这种数字的位置，假设序列长度为$n$，第一个该数字出现在位置$a_1$，这种数字有$m$个，假设计算在第一个数的位置上更靠前的排列个数，那么就应该是$\binom{n}{m}-\binom{n-a_1+1}{m}$，我们依此类推再计算在第二个数的位置上更靠前的排列个数之类的即可，可以做到$O(m)$计算。 计算完一类数字之后我们将所有这种数字删除再考虑剩下的数字，我们可以用树状数组维护前缀和来实现维护剩下数字的位置。 于是还剩下的就只有组合数无法轻易计算的问题了。。。 我们只能套用中国剩余定理来解决问题了0。0。 但是思路还蛮清晰的。

转载地址：https://blog.csdn.net/wyfcyx_forever/article/details/48446165 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！