i am trying to solve this problem but not getting idea can anybody help please with this problem
Most probably I overkilled the solution so feel free to ignore it, I’d appreciate if someone can share a neater solution.
So for any given N we have to calculate the following S,
S=1\&2+2\&3+3\&4+ \cdots + (N-1)\&N
S=
\underbrace{2\&3+4\&5+6\&7+ \dots }_\text{Even \& Odd} +\underbrace{1\&2+3\&4+5\&6 + \dots }_\text{Odd\& Even}
Now we will use the standard trick of bit manipulation. let c[i] be the number of terms where bit i is set. So final answer would just be
S=\displaystyle\sum_{i=0}^{60}c[i]*2^i
So all we need to do now is to find c[i] for all i's.
For any arbitrary i consider these 2 sub-cases.
CASE 1 (EVEN & ODD) :
In binary, any even number would look like E=100\underbrace{1}_\text{i}.....0 (some prefix of bits ending with a 0)
Then the next odd number just after E odd would look like O=100\underbrace{1}_\text{i}.....1 (same prefix ending with a 1)
Hence it’s pretty trivial to see that E\&O will have i th bit set if it’s set in E.
Observation 1: If any even number has i th bit set then its bitwise AND with next odd will contribute 1 to the bit count of i i.e. increase c[i] by 1
CASE 2(ODD & EVEN):
Similarly say, O=100\underbrace{1}_\text{i}..\underbrace{0}_\text{k}...1
Here k is the lowest unset bit of O
-
CASE A: k <i :
E=100\underbrace{1}_\text{i}..\underbrace{1}_\text{k}...0. It’s pretty clear that k would become the lowest set bit and bit i will be set in E if it was set in O. Hence O\&E will also contribute 1 to c[i] as in EVEN & ODD case. -
CASE B: k>i:
O=10\underbrace{0}_\text{k}\underbrace{1}_\text{i}.....1
E=10\underbrace{1}_\text{k}\underbrace{0}_\text{i}.....0
Now in this case i th bit will become unset and hence won’t contribute to the answer.
OBSERVATION 2: If any odd number has i th bit set then its bitwise AND with next even will contribute 1 to the bit count of i i.e. increase c[i] by 1 except for the case when all bits after i (including i ofc) are set..
So the final answer can be deduced by the following equation.
c[i]=F(N,i)-G(N,i)
F(N, i) - This returns the count of numbers that are less than equal to N and have their i th bit set. Note that we’ve added the contributions from both even and odd numbers in F(N,i).
G(N,i)- This returns the count of numbers that are less than N and have all bits set after i (including i )
And these functions are very trivial to compute. For F(N,i) you can refer this and G(N,i) would just be equal to N right shifted i+1 times .
Adding the code just for the sake of completeness.
AC_CODE
#include "bits/stdc++.h"
#define int long long
using namespace std ;
const int M = 1e9+7 ;
int pM(int b,int p){
int r=1 ;
for(;p;b=(b*b)%M,p/=2)
if(p&1)
r=(r*b)%M ;
return r ;
}
int F(int n, int i){
int ans = (n >> (i + 1LL)) << i;
if (((n >> i) & 1LL) != 0)
ans += n & ((1LL << i) - 1LL);
return ans%M;
}
int G(int n,int i){
return (n>>(i+1)) ;
}
void solve(){
int n,ans=0;cin >> n ;
vector<int>c(61) ;
for(int i=0;i<61;i++)
c[i]=F(n,i)-G(n,i);
for(int i=0;i<61;i++)
ans=((c[i]*pM(2,i))%M+ans)%M ;
cout << ans << '\n' ;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int TC ;
cin >>TC ;
while(TC--)
solve() ;
}
5 Likes
thank you very much bro
i think you should add this as editorial in problem so that people will get directly from their
request : could you explain the next question ( CodeChef: Practical coding for everyone) you can do that whenever you get free time and thanks again
1 Like
My approach was that for each bit we can calculate the no of valid pairs in which it is set.
So for any ith bit a valid pairs starts from its every odd multiple and its next 2^i-1 pairs are valid
For example for 4th bit, 2^4 = 16, so its first pair is (16,17 ) ,(17,18 ) … (30,31)…
then we next valid pair occurs at (48,49)(49,50)…(62,63) and then next occurs at (80,81).
So we can calulate easily no of odd factors of 2^i less than n and then for each of those we get (2^i-1) pairs and each of which adds 2^i to the answer
we get (n/2^i)/2 valid factors
but if (n/2^i) is odd then we get (n/2^i)/2 such points from which we get complete (2^i-1) pairs.
Apart from this we have to add some pairs seprately as we won’t get complete (2^i -1) pairs, but some of them.
E.g if n = 85, for 4th bit, 85/16 = 5, we get (5/2 = 2) complete ones, we also have to add contribution of (n-80) = (5) more pairs, which are from (80,81)…(84,85)
2 Likes