Could someone give some hint to this problem from ICPC Asia-Kharagpur Onsite Replay Contest 2018,
https://www.codechef.com/KGP18ROL/problems/PERIODCN
Since N can be 10^9, pre-calculating the solutions for values wont work.
I can’t think of any other strategy, help please.
This question required a bit of observation which can be got while looking at possible answers.
If you try to calculate answers carefully, you will notice that there aren’t many answers possible.
Consider this- They have asked various combinations of bits where length of consecutive runs of equal bits should be same.
Start from that length being 1 - then possible combinations of bits are 1,10,101,1010,10101 …
Start from length being 2 - then possible combinations are 11,1100,110011,11001100 …
Then to length being 3 - possible combinations are 111,111000,111000111 …
Now notice the constraint of r which is 10^9 that means log(r) will be at max 30.
So basically you have to do the above operation of finding possible answers only upto length being 30.
Also notice that while expanding the string , keep in mind that you need not expand after it reaches length 30 as numbers formed from that combination of bits is greater than 10^9.
So you can easily precompute an array of possible answers which are total of (1+1/2+1/3+…1/30)log(r) which is around 4log(r) (for r=10^9).
Just store the answers in decimals in an “ans” array rather than in bits which is crucial for the next part. Sort this array.
Now once you have your precomputed answers, time to move to each testcase -
For each test case- you need to find numbers in your ans array which satsify l<=x<=r for x in ans array. So now instead of just linearly searching for the answers , we can apply binary search (the reason why the ans array was sorted above). Thus the overall time complexity for each test case will be O(log(4log(r))) .
My code- link
@abhi2402 's answer completes everything. I would just add some more bits and parts to what I did and try to explain my solution-
1\le L,R\le10^9 make it obvious that the good old NLogN solution of iterating through all elements, then checking their binary form wont work 
.
However, the constraint that the groups must be of equal size is interesting. Lets say, that my current size of bits is K. Say I am debating on keeping size of each group p (where p \le K always). We can easily see that if p is not a multiple of K, then the grouping is not possible. also, for a particular group size p, we can have only 1 bit string for that K (Leading 0's not allowed!). This is a informal proof that going by “counting good pairs” is the way to go.
Since the max size of group is only 31 (as 2^{31}>10^9) I went the lazy way. For all group sizes i, I iterated through all numbers from 1 to i-1. Lets call them j. If I observe that j divides i, i.e. i\%j==0, then this is a valid size. I make the binary string of this size, and then convert it to decimal. Lets call this value A. I make a map and increment mp[A] by 1.
Code-
string s="";
char ch='1';
for(i=1;i<=31;i++)
{
for(j=i;j>0;--j)
{
if(i%j==0)
{
k=1;
s="";
ch='1';
while(k<=i)
{
s+=ch;
if(k%j==0)ch=('1'+'0')-ch;
++k;
}
int a=toInt(s);
//cout<<s<<"===>"<<a<<" i="<<i<<" j="<<j<<endl;
mp[a]++;
}
}
}
Recall the map which must have seemed highly redundant to you by now. 
. I made a map because, now, at this step, I can prefix sum entries of map like normal array.
Code for prefix sum-
for(;l!=mp.end();++l,++m)//l=mp.begin()+1,m=l-1 , i.e. previous index
{
(*l).second+=(*m).second;
}
Its all the same. If my entry of map is, say (4,1) where 4 represents the key/index and 1 represents the value at that index, and the next value is (10,1), then after prefix sum it will be [(4,1),(10,2)].
Dont worry if you dont know maps, the basic principle is, I did prefix sum so that mp[A] denotes number of such good numbers which are \le A. This allows us to answer queries in O(1) by mp[R]-mp[L-1] , i.e. Number of good numbers in [L,R] = Number of good numbers \le R - Number of good Numbers \le L-1
Now, for every query, I find the nearest entry of map which I filled, adjust endpoints. If after adjusting, they were A and B, then my answer was simply mp[B]-mp[A-1].
Code-
while(t--)
{
int l,r;
cin>>l>>r;
auto a=mp.lower_bound(l);
--a;
auto b=mp.upper_bound(r);
--b;
cout<<(*b).second-(*a).second<<endl;
}
(PS: I have not explained the map part in detail - I just stressed on the basic principle. I believe its you who should decide best how you want to implement the principle.).
Thank you so much, makes sense now.
I will try to implement.