"We know they lie between 0 and 2^32−1, i.e., they can be represented by 31 bits."
how its 31 bits…i think it can be a 32 bits integer,because after mod we can get max value of 2^32-1,which is a 32 bits integer.
pliz help @mgch
2 Likes
None of the sample solutions are opening…
Plz someone help me in this. I am unable to run this code. As O(10^8) memory can be allocated but this is O(10^10), though I know bitset takes 1/8 of actual memory but still order becomes O(10^9) still memory exhaustion remains.
However this code got accepted so plz help me in this.
@anonymous_b0y vector < bool > <-> bitset in C++ in terms of memory, vector < bool > v(N) use N / 8 bytes. Refer @mgch previous comments
Got AC … 
Can anyone please explain how to optimize this.Im getting TLE.
#include<bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
std::cin >> t;
long long mod=4294967296;
while(t--)
{
int q,s1,a,b;
cin>>q>>s1>>a>>b;
bitset<1000000002> bt;
// cout<<"created bitset "<<"\n";
long long prev=s1,num=0;
long long ans=0;
while(q--){
num=prev/2;
if(prev&1){
bt[num]= (bt[num] | 1);
}else{
bt[num] = (bt[num] & 0);
}
prev=(((a*prev)%mod)+(b%mod))%mod;
}
string s=bt.to_string();
for(int i=1000000001;i>0;i--){
ans+=(s[i]-'0');
}
cout<<ans<<"\n";
}
return 0;
}
While Calculating si=(si-1*a+b)mod2*32.We can get overflow in (si-1*a) as well right.Also not able to understand here how compiler handles overflow.can you please explain it