HDU 5565 Clarke and baton

Problem Description

Clarke is a patient with multiple personality disorder. One day, Clarke split into  guys, named  to .

They will play a game called Lose Weight. Each of Clarkes has a weight . They have a baton which is always in the hand of who has the largest weight(if there are more than 2 guys have the same weight, choose the one who has the smaller order). The one who holds the baton needs to lose weight. i.e.  decreased by 1, where is the guy who holds the baton.

Now, Clarkes know the baton will be passed 

Input

The first line contains an integer , the number of the test cases.

Each test case contains three integers ,  denotes the random seed.

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;      

Output

Each test case print a line with a number which is , where  is the 

Sample Input

1

3 2 1

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 10000005;
const int base = 1e9 + 7;
int T, limit;
int n, q, a[maxn], ft[maxn], nt[maxn];
LL seed;

int rand(int l, int r) {
    static long long mo = 1e9 + 7, g = 78125;
    return l + ((seed *= g) %= mo) % (r - l + 1);
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%I64d", &n, &q, &seed);
        int sum = rand(q, 10000000);
        limit = 0;
        for (int i = 1; i <= n; i++)
        {
            a[i] = rand(0, sum / (n - i + 1));
            sum -= a[i];
            limit = max(a[i], limit);
        }
        limit = max(limit, a[rand(1, n)] += sum);
        for (int i = 1; i <= max(limit, n); i++) ft[i] = nt[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            if (ft[a[i]])
            {
                nt[i] = ft[a[i]];
                ft[a[i]] = i;
            }
            else ft[a[i]] = i;
        }
        int tot = 0;
        for (int i = limit, j; i; i--)
        {
            if (q >= tot) { q = q - tot; limit = i; }
            else break;
            for (j = ft[i]; j; j = nt[j]) tot++;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
        if (a[i] >= limit) if (q) { ans ^= (limit + i - 1); q--; }
        else ans ^= (limit + i);
        else ans ^= a[i] + i;
        printf("%d\n", ans);
    }
    return 0;
}