Let $n$ be the number of digits in $x$ and $a(x)$ denote the number of times $f$ needs to be applied to $x$ for $x$ to reach $0$. Also, let $x_i$ be the $i$th (zero-indexed) digit of $x$ from the right, so that $x=x_{n-1}x_{n-2}\dots x_0$.

Subtask 1: It can be proven that $a(x)\in O(2^n)$, so just applying $f$ sequentially until $x$ reaches zero is sufficiently fast.

Full Solution: Let $S$ be the set of all non-negative integers whose digits consist solely of zeros and ones. We first note that either $x\in S$ or $f(x)\in S$, so it suffices to consider how $a(x)$ behaves for $x\in S$.

For $x\in S$, define $b(x)$ to be the (zero-indexed) rank of $x$ in $S$, which is just $b(x)=\sum_{i=0}^{n-1}x_i2^i$. Now for $x\in S$, let's try to relate $a(x)$ to $b(x)$.

• If the last digit of $x$ is one, then $f(x)\in S$ and $b(f(x))=b(x)-1$, $a(f(x))=a(x)-1$.
• Otherwise, $f^2(x)\in S$ and $b(f^2(x))=b(x)-1, a(f^2(x))=a(x)-2$.

So every time $b(x)$ decreases by two, $a(x)$ decreases by three. We can prove via induction that $a(x)=3\cdot (\sum_{i=1}^{n-1}x_i2^{i-1})+x_0$, which is very close to $3/2\cdot b(x)$. One way to get the remainder of $a(x)$ modulo $10^9+7$ is to first compute the remainders of $2^0, 2^1, \dots 2^{n-1}$ modulo $10^9+7$, then add the appropriate multiples of these values to the answer.

Time complexity: $O(n)$

Notes on avoiding overflow in the last two subtasks when using 32-bit integers:

• Take all intermediate results modulo $\texttt{MOD}=10^9+7$.
• Quantities as large as $3\cdot \texttt{MOD}$ can exceed the upper bound of a 32-bit integer. Use 64-bit integers (e.g., a long long in C++) to store these quantities instead.

Aidan Bai's C++ code:

#include "bits/extc++.h"
 
using namespace std;
 
using ll = long long;
 
#define sz(x) int(std::size(x))
 
constexpr ll mod = 1e9+7;
 
void solve(){
    string s;
    cin>>s;
    ll moves=0;
    int n=sz(s);
    ll tpow[n]{}; // powers of 2
    tpow[0]=1;
    for(int i = 1; i<n; i++){
        tpow[i]=(tpow[i-1]*2)%mod;
    }
    {
        // first make all digits 0 or 1
        bool all01=1;
        for(auto u: s){
            if(u!='0' && u!='1'){
                all01=0;
                break;
            }
        }
        if(!all01){
            moves++;
            for(auto &u: s){
                u=char(((u-'0')%2)+'0');
            }
        }
    }
    reverse(s.begin(),s.end());
    for(int i = 0; i<n; i++){
        if(s[i]=='1'){
            if(i==0)moves++;
            else{
                moves=(moves+tpow[i]+tpow[i-1])%mod;
            }
        }
    }
    cout<<moves<<"\n";
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(ios::failbit);
    int t;
    cin>>t;
    while(t--)solve();
}

Melody Yu's Python code:

MOD=1000000007
 
cost=[1]
sum=1
for i in range(1,200003):
    cost.append(sum+2)
    sum+=cost[i]
    sum%=MOD
 
t=int(input())
for _ in range(t):
    x=input()
    if x=='0':
        continue
    x=x[::-1]
    ans=0
    cnt=0
    for i in range(len(x)):
        v=ord(x[i])-ord('0')
        if v%2==1:
            ans+=cost[i]
            ans%=MOD
        if v!=0 and v!=1:
            cnt+=1
    if cnt>0:
        ans+=1
        ans%=MOD
    print(ans)