NOTATION:
- S is the binary string given.
- N is length of S.
- (A,B) is any valid pair such that conditions given hold true.
- X = A+B=A \oplus B
- D(S) is the decimal representation of binary string S.
- C(i) is the number of set bits in i.
- S[i \dots N] is the suffix of S after index i.
We can reduce the problem to find the following summation, since it is given in the problem that A+B \le D \implies X \le D. So we just have sum up the number of pairs for all possible values of X. i.e. the following summation.
But how to find this? obviously, we canât naively iterate overall all values from 0 to 2^N where N\le 10^5.
So weâll use digit dp to find R.
DIGIT DP STATES AND TRANSITIONS:
DP[i] â \displaystyle \sum_{k=0}^{D(S[i \dots N])}2^{C(k)} i.e. Sum of 2^{C(k)} for all 0 \le k \le D(S[i \dots N]) in the suffix of S after index i.
Transitions are pretty straightforword.
IF S[i]=0:
Then itâd be the same as the answer we obtained at index i+1 (Since we have no option but to put a zero in here otherwise itâll be greater than D(S[i \dots N])
IF S[i]=1:
Now we can put either a zero or a 1 at index i.
If we happen to put a 0 then for the entire suffix from i+1 to N we can have any number of set bits we want. So the number of numbers with k set bits would just be \displaystyle \binom{N-1-i}{k} but since the contribution of each number with k set bits is 2^k so total contribution would be \displaystyle \sum_{k=0}^{N-1-i}\binom{N-1-i}{k}2^k
But what if we put a 1 at index i then it is clearly evident that it is the sub subproblem for suffix from i+1 that we solved already i.e. DP[i+1] but with one extra set bit so the contribution from this subpart will be 2 \times DP[i+1]. So the transition will look like.
Base case is DP[N]=1 and final answer R would just be DP[0].
ASYMPOTICS.
Time & Space complexity for this solution is \mathcal{O}(N)
CODE FOR REFERENCE
#include "bits/stdc++.h"
#define ll long long
using namespace std ;
const int M = 1e9+7,mxN=1e7;
int dp[mxN+1] ;
ll pM(ll b,int p){
ll r=1 ;
for(;p;b=(b*b)%M,p/=2)
if(p&1)
r=(r*b)%M ;
return r ;
}
int main(){
string s ; cin >> s ;
int n = s.size() ;
dp[n]=1;
for(int i=n-1;~i;--i)
dp[i]=(s[i]=='0'?dp[i+1]:(2*dp[i+1]+pM(3,n-1-i))%M) ;
cout << dp[0] ;
}
Solutions that involve converting the entire string to integer as presented by @suman_18733097, wonât work for strings greater than length 10^4(thanks to python, C++ wouldâve failed to handle strings of length 60 ) it is because youâre essentially storing 2^{10^5} in int data type which is way way too much!!.
