Official Analysis (C++, Python)

Explanation

One can observe that the answer for $10^a$ is $3 \cdot 2^{a - 1}$ for $a > 0$ (in other words, a geometric sequence starting at three with common ratio two). Note that this doesn't apply to $a = 0$, because the answer for $x = 1$ is $1$.

To see why this is true, consider the function $B(n)$ which denotes the decimal number whose digits are the binary representation of $n$. Particularly, $10^a = B(2^a)$. If $x = B(n)$, the first call subtracts one in decimal, and the next call converts the resulting digits by parity if $n$ is even. Thus, for $n \ge 1$, if $n$ is odd then one $f$ call sends $B(n)$ to $B(n - 1)$, and otherwise if $n$ is even then two $f$ calls send $B(n)$ to $B(n - 1)$.

An example to illustrate the odd $n$ case is $B(13) = 1101, f(1101) = 1100 = B(12)$. Only one $f$ operation is needed for odd $n$ because by definition, the binary representation of odd $n$ ends in one, which turns to zero. On the other hand, $B(12) = 1100, f(1100) = 1099, f(1099) = 1011 = B(11)$, so even $n$ needs a second call.

Thus, $\operatorname{ans}(10^a)$ = $\sum_{n=1}^{2^{a}}\left(1\ \operatorname{if}\ n\ \operatorname{odd},\ 2\ \operatorname{if}\ n\ \operatorname{even}\right) = 3 \cdot 2^{a - 1}$.

Any number in a binary state is just the sum of powers of ten, corresponding to the positions of its one digits. Operations on the lowest power of ten do not affect higher powers of ten while handling it, so the contributions from the different one bits can be computed and added independently. For example, $\operatorname{ans}(10110) = \operatorname{ans}(10000) + \operatorname{ans}(100) + \operatorname{ans}(10)$.

Our algorithm is as follows: convert $x$ to binary with one $f(x)$ operation if it isn't already. Then, loop through the digits and add up the contributions for the ones. If the $i$th (zero-indexed) digit is one, the power of ten this corresponds to is $\operatorname{len}(x) - i - 1$. To handle overflow, apply the modulo at each intermediate step and precompute powers of two modulo.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
MOD = 10**9 + 7
for _ in range(int(input())):
	x = list(input())
	n = len(x)
	answer = 0

	# make digits binary if not already
	if not all(c in "01" for c in x):
		answer = 1
		for i in range(n):