2015
07-25

# Circle Game

You must have some knowledge with circle games in ACM problems, such as Joseph Ring problem. Today we are going to introduce a new circle game described as follows. There is a circle which contains M points, numbered from 0 to M-1. At first, n students stand in different points of the circle. It is possible that more than one student stand in the same point. For each second, each student moves one step forward in clockwise direction. The following picture gives us an example of that M equals to 8 and n equals to 3. Initially, the first student S1 stands in the point 0, the second student S2 stands in the point 2 and the third student stands in the point 7. After 2 seconds, they will change their positions as the right part of the picture.

At the beginning of the game, Tracy writes down the positions of all students. Then he will go to sleep and students will abide by the above rules to make this game run until Tracy wake up. After a period of time, Tracy wakes up. He finds it is very hard to identify where the first student S1 stands in and where the second student S2 stands in and so on, because all students are the exactly similar and unable to be distinguished. So Tracy records all the positions of students and writes down the XOR sum of these positions (The XOR sum of an array A means A[0] xor A[1] xor … A[n-2] xor A[n-1] and xor is the exclusive or operation, for example 0111 xor 1011 = 1100). Now Tracy wants you to help him to know how many seconds he had slept. To simplify the problem, the number of points is always a power of 2 like 2m.
Furthermore, Tracy knows that the time he slept is not greater than T. Please note that the time Tracy slept must be greater than zero. There may have many different periods of time corresponding with the above conditions.

There are several test cases, each test case firstly contains four integers n, m, S, T. S is the XOR sum of students’ positions when Tracy wakes up. Another 3 integers n, m, T are described as the above. Then n integers will follow in the next line, which represent the positions of students initially. The input will finish with the end of file.
0 < n <= 100000, 0 < m <= 50, 0 <= S< 250, 0 < T <= 1016 and the student position is in the range [0, 2m).

There are several test cases, each test case firstly contains four integers n, m, S, T. S is the XOR sum of students’ positions when Tracy wakes up. Another 3 integers n, m, T are described as the above. Then n integers will follow in the next line, which represent the positions of students initially. The input will finish with the end of file.
0 < n <= 100000, 0 < m <= 50, 0 <= S< 250, 0 < T <= 1016 and the student position is in the range [0, 2m).

3 3 7 5
0 2 7
5 3 7 5
1 2 3 4 5
4 4 0 10
1 3 5 7
6 5 18 100
22 10 18 20 2 10

1
0
4
50
Hint

For the first test case, the following table explains that only “2 seconds” matched the restrictions.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <vector>
#include <ctime>
using namespace std;

typedef long long LL;
const int N = 100000;
const int M = 50;
const LL MAXS = 1LL<<50;
const LL MAXT = (LL)1e16;

inline LL two( int x ) { return 1LL<<x; }

// f means <=, g means >
LL  f[M+1][N+5], g[M+1][N+5], a[N+5];
int rank[2][2][N+5];
int n , m;
LL  s;

void solve( LL t , LL &ans1, LL &ans2) {
fill( f[0], f[0]+n+1, 0 );
fill( g[0], g[0]+n+1, 0 );
f[0][0] = 1;
int bits[55], bitt[55];
for( int i = 0 ; i < m; ++i ) {
bits[i] = (s&two(i))>0;
bitt[i] = (t&two(i))>0;
}

rank[0][0][0] = n;
rank[0][1][0] = 0;
for( int i = 1; i <= n; ++i ) {
rank[0][0][i] = i-1;
}

for( int i = 1; i <= m; ++i ) {
int cur = i&1, pre = cur^1 ;
fill( f[i], f[i]+n+1, 0 );
fill( g[i], g[i]+n+1, 0 );

// radix sort, from large to small
for( int j = 0 ; j < 2; ++j ) rank[cur][j][0] = 0;
for( int j = 1 ; j >= 0; –j ) {
for( int k = 1 ; k <= rank[pre][j][0]; ++k ) {
int idx = rank[pre][j][k];
if( a[idx] & two(i-1) ) rank[cur][1][ ++rank[cur][1][0] ] = idx ;
else rank[cur][0][ ++rank[cur][0][0] ] = idx ;
}
}

int oneCnt = 0, curOnes = rank[cur][1][0], curZeros = rank[cur][0][0];
// update i bit with i-1 bit
for( int j = 0; j <= n; ++j ) {
int idx = -1, presize1 = rank[pre][1][0];
if( j > presize1 ) {
idx = rank[pre][0][j-presize1];
} else {
if( j > 0 ) idx = rank[pre][1][j];
}

// when j = 0 ==> idx = -1;
if( idx != -1 && (a[idx]&two(i-1)) != 0 ) {
++oneCnt;
}
int tBit = bitt[i-1];

// do nothing
int curOne = curOnes + j – 2*oneCnt;
if( (curOne&1) == bits[i-1] ) {
if( tBit == 0 ) {
f[i][ oneCnt ] += f[i-1][j];
g[i][ oneCnt ] += g[i-1][j];
} else {  // less than
f[i][ oneCnt ] += f[i-1][j]+g[i-1][j];
}
}

curOne = curZeros – j + 2*oneCnt;
int nextOne = j + curOnes – oneCnt;
if( (curOne&1) == bits[i-1] ) {
if( tBit == 0 ) {
g[i][ nextOne ] += g[i-1][j] + f[i-1][j];
} else {  // less than
f[i][ nextOne] += f[i-1][j];
g[i][ nextOne] += g[i-1][j];
}
}
}

//for( int j = 0; j <= n; ++j )  cout<<i<<” “<<j<<” “<<f[i][j]<<” “<<g[i][j]<<endl;
}
ans1 = ans2 = 0;
for( int i = 0 ; i <= n; ++i ) {
ans1 += f[m][i];
ans2 += g[m][i];
}
ans2 += ans1;
return ;
}

int main() {
LL  t;
//freopen(“CircleGame.in”,”r”,stdin);
//freopen(“large.out”,”w”,stdout);
int start = clock();
//cout<<MAXT<<” “<<MAXS<<endl;
while( scanf(“%d%d%lld%lld”,&n,&m,&s,&t) != EOF ) {
//assert( n > 0 && n <= N );
//assert( m > 0 && m <= M );
//assert( s >= 0 && s < MAXS );
//assert( t > 0 && t <= MAXT );
if( t > MAXT ) {
cerr<<t<<” “<<MAXT<<endl;
}
LL x = 0;
for( int i = 0 ; i < n; ++i ) {
scanf(“%lld”,&a[i]);
x ^= a[i];
//assert( a[i] >= 0 && a[i] < 1LL<<m );
}

LL M = 1LL << m, loops = t/M;
LL ans1, ans2;
solve( t%M ,ans1, ans2);
loops *= ans2;
loops += ans1;
if( x == s ) loops–;
printf(“%lld\n”, loops);
//printf(“ans1=%lld %lld\n”, ans2, loops);
}
//printf(“%lf\n”,(clock()-start)*1.0/CLOCKS_PER_SEC);
return 0;
}