Observe & Analyse

我们先来手动计算一下 $f(1010)$：

• $1009$
• $1001$
• $1000$
• $999$
• $111$
• $110$
• $109$
• $101$
• ...

剩下的没有必要计算下去，我们已经发现了本题最重要的结论：如果将仅含 $0$ 或 $1$ 的数字视作二进制数，那么每操作 $3$ 次，它的值会减少 $2$。

那么做法就非常简单了：

• 如果数字中含有非 $0$ 或 $1$ 的数，操作一次。
• 如果数字在十进制下不是偶数，操作一次。
• 将数字乘上 $\frac{3}{2}$ 并加入操作数。
• 别忘记取模！

因为数字非常大，需要按位处理，具体的实现细节还要看代码。

Code

考场代码。

/*
ID:Terabyte
TASK:test
LANG:C++
*/
#include<bits/stdc++.h>
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl '\n'
#define mod 1000000007
using namespace std;

ll f[200005]={1};

void solve(){
	string s;
	ll res=0;
	cin>>s;
	int len=s.size();
	for(int i=0;i<len;i++){
		if(s[i]!='0' && s[i]!='1'){
			res=1;
			s[i]=(s[i]-'0')%2+'0'; //有非0或1的数，操作一次
		}
	}
	if(s[len-1]=='1'){
		s[len-1]='0';
		res++; //末尾是1，不是偶数，操作一次
	}
	for(int i=0;i<len-1;i++){
		if(s[i]=='1'){
			res+=f[len-i-2]*3; //从低位到高位
			res%=mod;
		}
	}
	cout<<res<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	int t;
	for(int i=1;i<=200000;i++) f[i]=f[i-1]*2%mod; //预处理2的次方
	cin>>t;
	while(t--) solve();


	return 0;
}