题目
给定一个n,p(2<=p<=n<=1e5)，保证p是素数
以下一个长度为n的数组a[]，第i个数ai(1<=ai<=1e9)，代表第i个人手中的糖果数
设Yuzu初始有x块糖，以下Yuzu要参加一个比糖果多少的游戏，
她可以预先指定这个比的顺序，也就是1-n这n个人的排列，
如果Yuzu的糖大于等于对方的糖，Yuzu就赢了，
并且本轮中还会获得一块糖，然后再比下一轮
Yuzu想赢得所有的n轮游戏，设能满足其要求的n个人的排列数为f(x)
若f(x)不是p的倍数，则称x是"好"的，
求"好"的x的个数，并输出所有的x
思路来源
1、2来自官方题解，3来自题解下方评论区及群友
题解
1、2：
设mx=max{ai}，也就是最多的糖果数
首先，注意到，（不要在意等号这些细节，可能会差1）
所需的糖数x不会少于mx-n，否则把mx放到最后一位也比不赢，
也就意味着所有的场次都比不赢， f(x)=0，%p==0
所需的糖数x不会多于mx，否则怎么安排顺序都会赢，f(x)=n!，%p==0
也就是，只需要在[mx-n,mx]这个长度为n的区间检查答案
记num[i]为糖果数不超过i的人数，，
对应了i从0到n-1时，当前糖果数为x+i时，每次num[x+i]-i个人可以挑战
f(x)不为p整除，令g(i)=num[x+i]-i，即任意g(i)都不为p整除，则g(i)取值应均在[1,p-1]，
考察g函数的性质，
若固定x，前一项随着i的增加而递增（非严格），后一项减1，所以g(i)要么递增，要么最多减1，
若对于某一个x，画出g的函数图像，发现x递增的时候，函数图像会向上平移（非严格），
即在时的g(i)，一定不超过时的g(i)，
所以，答案应该是连续的一段，从某个值函数图像均落在[1,p-1]起，到往上平移，挪出这个区间
题解1：
令x的左界lb=mx-n+1，如果对于当前i，num[lb+i]-i<1，说明应该增加下界，使g(i)更大，
不断增lb，直至当前的i合法，再检查下一个i
令x的右界ub=mx-n+n，如果对于当前i，num[lb+i]-i>=p，说明应该减小上界，使g(i)更小，
不断减lb，直至当前的i合法，再检查下一个i
题解2：
考虑，以x+i代换i，有
即给定x，对于所有的i，都不存在i，满足
对于x=lb，其需要检查[lb,lb+n-1]的i，
对于x=lb+1，其需要检查[lb+1,lb+n]的i，
注意到只有左右界的单点修改，区间滚动
那么，就预先把x=lb的对应的n个插入桶中，判断x=lb是否合法，
再更改一下左右界，再检查lb+1，依次类推，直至检查完ub，
题解3：
先将a数组从小到大排序，则num[x+i]-i<p，即num[x+i]<p+i，排序后的数组中有num[a[p+i-1]]=p+i，
即恰满足能战胜p+i个的下界是x=a[p+i-1]，说明num[x+i]<num[a[p+i-1]]，有x+i<a[p+i-1]，即x<a[p+1-i]-i
对于所有p+1-i合法的下标，检查该不等式，取min即得上界ub
下界同理，由于num[x+i]-i>=1，有num[x+i]>=i+1=num[a[i]]，即x+i>=a[i]，x>=a[i]-i，
对于所有i合法的下标，检查该不等式，取max即得下界lb
心得
一个题补了一天gg，发现性质很重要，然而着手怎么做也很重要，
本题性质：num[x+i]-i>=1，num[x+i]-i<p，x只可能在[mx-n,mx]之间
代码1
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int n,p,a[N],num[M],mx,lb,ub;
int main(){
scanf("%d%d",&n,&p);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
mx=max(mx,a[i]);
}
//mx-n<=x<=mx 偏移量挪动到[0,n]
for(int i=0;i<n;++i){
num[max(0,a[i]-(mx-n))]++;
}
for(int i=1;i<M;++i){
num[i]+=num[i-1];
}
lb=1;
//num[n+n] 所以用二倍下标
for(int i=0;i<n;++i){
while(num[lb+i]-i<1){
lb++;
}
}
ub=n;
for(int i=0;i<n;++i){
while(ub>0 && num[ub+i]-i>=p){
ub--;
}
}
if(lb>ub)puts("0");
else{
printf("%d\n",ub-lb+1);
for(int i=lb;i<=ub;++i){
printf("%d ",i+(mx-n));
}
}
return 0;
}
代码2
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int n,p,a[N],num[M],mx;
int res[N],c,now[N];
int f(int x,int y){
return (x%y+y)%y;
}
int main(){
scanf("%d%d",&n,&p);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
mx=max(mx,a[i]);
}
//mx-n<=x<=mx 偏移量挪动到[0,n]
for(int i=0;i<n;++i){
num[max(0,a[i]-(mx-n))]++;
}
for(int i=1;i<M;++i){
num[i]+=num[i-1];
}
for(int i=0;i<n;++i){
now[f(i+(mx-n)-num[i],p)]++;
}
for(int i=0;i<=n;++i){
if(now[f(i+(mx-n),p)]==0){
res[++c]=i+(mx-n);
}
now[f(i+(mx-n)-num[i],p)]--;
now[f((n+i)+(mx-n)-num[i+n],p)]++;
}
printf("%d\n",c);
for(int i=1;i<=c;++i){
printf("%d ",res[i]);
}
return 0;
}
代码3
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,p,a[N],lb,ub;
int main(){
scanf("%d%d",&n,&p);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
ub=max(ub,a[i]);
}
sort(a,a+n);
for(int i=0;i<n;++i){
lb=max(lb,a[i]-i);
}
for(int i=0;p+i-1<n;++i){
ub=min(ub,a[p+i-1]-i-1);
}
if(lb>ub)puts("0");
else{
printf("%d\n",ub-lb+1);
for(int i=lb;i<=ub;++i){
printf("%d ",i);
}
}
return 0;
}
