此题使用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;
}