此题使用dp的思想,记录之前所有的方案,然后看要加入的数能否构成答案,如果可以就加入答案,并计算这个数能构成的方案
用ans记录答案数,cnt记录前面能构成的数的个数
假设第一位为0,显然此时ans=1,那cnt为多少呢?假设为1,那就会构造出01,02这种不合法的数,故cnt为0
我们以第一位为1,模拟一下,ans=0,cnt=1
加入的数为0时,能构成的数0,1,10,即ans+cnt+1,前导0不计入cnt,cnt*2
加入的数为2时,能构成的数0,1,10,12,102,2,即ans+cnt+1,cnt*2+1
加入的数为3时,能构成的数0,1,10,12,102,2,13,103,123,1023,23,3,即ans,cnt*2+1
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
int n;
string str;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> str;
ll ans=0,cnt=0;
for(int i=0;i<n;i++){
if(str[i]=='0'){
ans=(ans+cnt+1)%mod;
cnt=(cnt*2)%mod;
}else if((str[i]-'0')&1){
cnt=(cnt*2+1)%mod;
}
else {
ans=(ans+cnt+1)%mod;
cnt=(cnt*2+1)%mod;
}
}
cout << ans;
return 0;
}