HDU5565

【中文题意链接】

【分析】其实是个水题，用一个可变数组(vector或者链表)来记录每个a[i]对应的所有下标，很容易可以通过预处理让每个链表内下标都有序，然后每次传递接力棒的时候只要让a[i]链表最小的值移动到a[i-1]链表，但是移动的时候不是会使得a[i-1]不是有序了？没关系，只要在剩余传递次数小于当前链表内元素个数的时候才会产生影响，那么这个时候只要把这个链表内元素排一次序即可，由于每个元素最大只有10^6，所以可以通过计数排序做到O(N)复杂度，那么总的复杂度还是O(N)的。这里链表我用了链式前向星来存既剩内存还提高效率。

【AC CODE】889ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 10000000+10,MAXM = 10000000*2+10;
int head[MAXN],sz[MAXN],tol,nxt[MAXM],to[MAXM];
int a[MAXN];

long long seed;
int rand(int l, int r) {
	static long long mo=1e9+7, g=78125;
	return l+((seed*=g)%=mo)%(r-l+1);
}
inline void add_edge(int u, int v)
{
	nxt[tol] = head[u],to[tol] = v;
	if(-1 == head[u]) sz[u] = 1;
	else sz[u]++;
	head[u] = tol++;
}
int cnt[MAXN],num[MAXN];
void my_sort(int id)
{
	int mx = 0,s = 0;
	clc(cnt,0);
	for(int i = head[id]; ~i; i = nxt[i])
	{
		num[s++] = i;
		cnt[to[i]]++;
		mx = max(mx,to[i]);
	}
	s = 0;
	repe(i,0,mx)
	{
		while(cnt[i]) to[num[s++]] = i,cnt[i]--;
	}
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n,q,mx = 0;
		scanf("%d%d%lld",&n,&q,&seed);
		int sum=rand(q, 10000000);
		for(int i=1; i<=n; i++) {
			a[i]=rand(0, sum/(n-i+1));
			sum-=a[i];
		}
		a[rand(1, n)]+=sum;
		/*n = 4,q = 3;
		a[1] = 2,a[2] = 2,a[3] = 3,a[4] = 2;*/
		repe(i,1,n) mx = max(mx,a[i]);
		tol = 0;
		clc(head,-1);
		per(i,n,1) add_edge(a[i],i);
		int p = mx,sot = false;
		rep(i,0,q)
		{
			while(!sz[p]) p--;
			if(!sot && q-i < sz[p])
			{
				my_sort(p);
				sot = true;
				//continue;
			}
			int &h = head[p];
			int id = to[h];
			sz[p]--;
			h = nxt[h];
			add_edge(p-1,id);
		}
		int ans = 0;
		repe(i,0,mx)
		{
			for(int j = head[i]; ~j; j = nxt[j])
				ans ^= (i+to[j]);
		}
		printf("%d\n", ans);
	}
	return 0;
}