题目
https://codeforces.com/contest/1371/problem/E2
有一个游戏，规则如下：
- 有n个敌人，第i个敌人能力值为a[i]。你的初始能力值为x。
- 如果你的能力值>=敌人的能力值，你可以击败他。
- 当你击败一个敌人后，你的能力值+1。
- 你任意调整打敌人的顺序（即n的全排列种）。设f(x)为可以击败所有敌人的顺序方案数。
现在，给定n和a，以及一个整数p（0<p<=n），求所有的x，使得f(x)不能被p整除。
做法
首先肯定先将a[i]排序。那么，要击败所有敌人，x至少为max{a[i]}-n+1。而由于0和n!可以被p整除，所以必有max{a[i]}-n+1 <= x <= max{a[i]}-1。也就是说，可取的x最多只有n-2个。
通过手算可以发现，设b[i]为可以放在i位置之前的敌人数，那么$f(x)=\prod_{i=0}^{n-1}(b[i]-i)$。而当x增大1时，b[i]会变成b[i+1]。
这里一定要好好利用题目的性质。我们要求出哪些f(x)不能被p整除。我这里就在想怎么维护所有的b[i]-i模p的值，想了很久也没想出来。其实这题很简单，因为最后乘的一项一定是1，而b[i]-i最多只会减少1，所以只要有某一个b[i]-i大于等于p了，就一定会被p整除。
同时，由于x增大1，b[i]变为b[i+1]，而b数组肯定是不降的，因此如果f(x)>0能被p整除，那么比x大的都一定会被p整除。
所以，我们先确定最小的f(x)>0的x，然后二分查找右端点即可。每次O(n)看一下所有的b[i]-i是否满足条件即可。时间复杂度O(nlogn)。