This is a pretty cool problem and it is actually not as hard as it looks.
The essential idea of these type of combinatorial games is SPRAGUE-GRUNDY-NUMBER.
Here is a link to a more detailed description
I think most people have played NIM before, a game with many pile of stone. You can choose any pile of stone(only one) and take any number of stone from it. The person who takes the last stone wins.
There is no tie in the game, so any state is either Next player win or Previous player win.(The player that is going to make a move in this state is considered as Next player)
We will write them as N and P. If you can move to P state, you are a N state. If you can't, you are in a P state.
In Nim, if the XOR of all pile of stone is 0, then it is a P state. If not, it is a N state.
And any combinatorial game can actually transform into Nim, using the Sprague-Grundy-Theorem.
For example:(in this problem)
We consider a pair of integer as a pile of stone.
(l, r)
If r-l <= 2, then it is considered as a 0 stone pile.
If after making a move, this pair can transform into a 0 stone pair, then it is considered as a 1 stone pile.
If after making a move, this pair can transform into a 0 stone pair or a 1 stone pair, then it is considered as a 2 stone pile.
And you just need to find how many combination so that the xor of all these n pair is not 0.
It can be done using simple dp method.
=======================================================================
So know the problem is how are you going to find the grundy number of a pair.
First, you can discover that the pairs with same r-l, can be seen as the same.
It is pretty obvious, you can find it after a bit of thinking.
And the discovery above, reduces its calculating amount from O(P^2) to O(P).
(Hoooooray~)
But P can be as big as 10^9, so we are still not there but is almost there.
The last discovery is that the grundy number sorted with r-l, forms block.
I figure this out after printing the first 1000 number with the code below.
//By momo
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10000]; //dp[i] is the grundy number of (l,r) with r-l = i
int cal(int a, int b){
if(dp[a] != 0 && dp[b] != 0) return 0;
if(dp[a] != 1 && dp[b] != 1) return 1;
return 2;
}
int main (){
dp[1] = dp[2] = 0;
for(int i = 3; i <= 20; i++){
int v = i/3, u = i-v;
dp[i] = cal(u, v);
printf("%d\n", dp[i]);
}
}
The first twenty is like this: 0, 0, 1, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2, 0, 0
Even though the first 20 is messy, there is only about 100 blocks in 10^9 number.
So the last part is to calculate the block, the detail is really complicated, but its only complicated not hard.
If you want to see the code, here is my submission. 3222085
