C++14(g++5.4) 解法, 执行用时: 41ms, 内存消耗: 6140K, 提交时间: 2020-09-24 19:25:08

#include<bits/stdc++.h>
using namespace std;


#define ull unsigned long long 

const int N=100005;
int n,m,k;
int a[N];
const ull base=100007;
ull b[N],h[N];
vector<int>v[N];


int solve(int s1,int s2,int add){
	int l=0,r=n,mid,ans=0;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(h[s1]-h[s1+mid]*b[mid]==h[s2]-h[s2+mid]*b[mid])ans=mid,l=mid+1;
		else r=mid-1;
	}
	if(ans==n)return s1;
	return (a[s1+ans]+add)%m<(a[s2+ans]+add)%m?s1:s2;
}

void init(){
	b[0]=1;
	for(int i=1;i<=2*n;i++)b[i]=b[i-1]*base;
	for(int i=2*n-1;i>=0;i--)h[i]=h[i+1]*base+a[i];
}

int main(){
	cin>>n>>m>>k; 
	k--;
		
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i+n]=a[i];
		v[m-a[i]].push_back(i);
	}
	
	init();
	
	int ans=0;
	for(int i=1;i<n;i++)ans=solve(ans,i,0);
	printf("%d\n",a[ans+k]);
	
	for(int i=1;i<m;i++){
		if(v[i].size()){
			ans=v[i][0];
			for(int j=1;j<v[i].size();j++)ans=solve(ans,v[i][j],i);
		}
		printf("%d\n",(a[ans+k]+i)%m);
	}
	
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 47ms, 内存消耗: 5080K, 提交时间: 2020-08-14 18:26:22

#include<bits/stdc++.h>
using namespace std;

unsigned long long Hash[100005]={0},Power[100005],base=1e9+7;
int n,m,k,a[100005];
vector<int>R[50005];
int get(int x,int y,int t)
{
	int l,r,mid,ans;
	for(l=0,r=n;l<=r;)
	{
		mid=(l+r)>>1;
		if(Hash[x+mid-1]-Hash[x-1]*Power[mid]==Hash[y+mid-1]-Hash[y-1]*Power[mid])ans=mid,l=mid+1;
		else r=mid-1;
	}
	if(ans==n)return x;
	if((a[x+ans]+t)%m<=(a[y+ans]+t)%m)return x;
	return y;
}
int main()
{
    int i,j,ans=1;
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i],R[m-a[i]].push_back(i);
    for(Power[0]=i=1;i<=2*n;i++)Power[i]=Power[i-1]*base,Hash[i]=Hash[i-1]*base+a[i];
    for(i=2;i<=n;i++)ans=get(ans,i,0);
    printf("%d\n",a[ans+k-1]);
    for(i=1;i<m;i++)
    {
    	if(R[i].size())for(ans=R[i][0],j=1;j<R[i].size();j++)ans=get(ans,R[i][j],i);
    	printf("%d\n",(a[ans+k-1]+i)%m);
	}
    return 0;
}