Problem Link
Author: aryansanghi
Solution
Observation
- The maximum number of set bits is 2000. So, we can precompute F(N) for all N in [1,2000] recursively by using F(1) = 0 and F(N)=F(H(N))+1.
Algorithm
- Precompute values of F for integers from 1 to 2000.
- Start moving from MSB to LSB. If the current bit is set bit and is the k^{th} MSB, let the number of bits after the current bit be x and let the number of set bits till now(excluding current set bit) be y. For all values of i from 0 to x(inclusive), add (F(i+y)+1)\times(^xC_i) to the answer.
Code
//Written By Aryan Sanghi
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<queue>
#include<utility>
#include<set>
#include<unordered_map>
using namespace std;
#define ll long long int
#define rep(i, n) for(ll i = 0; i < n;i++)
#define repi(i, a, n) for(ll i = a;i < n;i++)
#define repii(i, a, n, b) for(ll i = a;i < n;i += b)
#define mod 1000000007
#define pb push_back
vector<vector<ll> > v;
vector<ll> cp;
ll gcd(ll a, ll b)
{
if(b == 0)
return a;
if(a == 0)
return b;
if(a > b)
return gcd(b, a % b);
return gcd(a, b % a);
}
ll maxi(ll a, ll b)
{
if(a > b)
return a;
else
return b;
}
ll mini(ll a, ll b)
{
if(a > b)
return b;
else
return a;
}
int modpower(ll a, ll b, ll c)
{
ll r=1;
a=a%c;
while(b>0)
{
if(b%2==1)
r=(r*a)%c;
b=b/2;
a=(a*a)%c;
}
return r;
}
int main()
{
ll t;
cin>>t;
ll f[2001];
f[0]=0;
f[1]=0;
repi(i, 2, 2001) {
ll count = 0, temp=i;
while(temp>0){
count+=temp%2;
temp/=2;
}
f[i]=f[count]+1;
}
ll fact[2001];
fact[0] = 1;
repi(i, 1, 2001) fact[i] = (fact[i-1]*i)%mod;
while(t--)
{
string s;
cin>>s;
ll n = s.size();
vector<ll> a(n+1, 0);
ll count = 0;
rep(i, n){
if(s[i]=='1'){
repi(j, count, count+(n-i)){
ll x=n-i-1, y=j-count;
ll k=fact[x];
k*=modpower(fact[y], mod-2, mod);
k%=mod;
k*=modpower(fact[x-y], mod-2, mod);
k%=mod;
a[j]+=k;
a[j]%=mod;
}
count++;
}
}
a[count]+=1;
a[count]%=mod;
ll ans=0;
a[1]--;
repi(i, 1, n+1) {
// cout<<a[i]<<" "<<f[i]<<"\n";
ll k=a[i]*(f[i]+1);
k%=mod;
ans+=k;
ans%=mod;
}
// cout<<"\n";
cout<<ans<<"\n";
}
}