Clarke and baton

Accepts: 1
Submissions: 126
Time Limit: 12000/6000 MS (Java/Others)
Memory Limit: 524288/524288 K (Java/Others)
问题描述
克拉克是一名人格分裂患者。某一天,克拉克fork出了$n$个自己,序号从$1$到$n$。
他们准备玩一个减肥游戏,每一个克拉克都有一个体重$a[i]$。他们有一个接力棒,这个接力棒任何时刻总是在最重的克拉克(如果重量相同则在序号最小的)的手中,得到这个接力棒的克拉克需要减肥,使得体重变成$a[i]-1$,随后接力棒便传递到下一个人(可以是自己)的手中。
现在克拉克们知道接力棒一共被传递过$q$次,他们想知道最终每一个克拉克的体重分别是多少。
输入描述
第一行一个整数$T(1 \le T \le 10)$,表示数据的组数。
每组数据只有一行三个整数$n, q, seed(1 \le n, q \le 10000000, \sum n \le 20000000, 1 \le seed \le 10^9+6)$,分别表示克拉克的个数、接力棒传递次数还有一个随机种子。
$a[i]$按照以下规则生成:

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);
}

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;
输出描述
每组数据输出一行一个数,这个数$ans$是这样得到的。
假设$b[i]$是最终克拉克们的体重,则$ans=(b[1]+1) xor (b[2]+2) xor ... xor (b[n]+n)$,其中$xor$是异或操作。
输入样例
1
3 2 1
输出样例
20303
Hint
首先$a[1]=20701, a[2]=31075, a[3]=26351$
第一次接力棒在$2$号克拉克手上,所以$a[2]=31074$。
第二次接力棒在$2$号克拉克手上,所以$a[2]=31073$。
所以答案等于$(20701+1)xor(31073+2)xor(26351+3)=20303$