C 的另类解法（无需任何算法）

简述 ：

对于任意一个 01 串， 我们都可以不断忘上一层推， 直至字符串收敛为只有一个字符或者无解

所以答案就是 不同层数的 0 或 1 的数量之和.

对于任意一个字符串，在掐头去尾的情况下，中间的部分往回推是只有唯一的情况的，只要存在有 1 的情况，字符串就一定会收敛，反之只要有两个零存在 即 00 , 无解， 直接结束。

对于开头

如果开头是 1 , 对应的可能是 0 , 也可能是 1 （其实这个时候已经和中间部分的地位无异了， 所以只需特判 0）, 开头是 0 , 则是 1,

对于中间部分

10 串出现对应 1 , 只有 1 就是 0

对于结尾

结尾是 0 ，那么必然会在中间部分判断完成

如果是 1 , 那就存在两种情况， 即 0 和 1

复杂度分析

收敛情况最慢的字符串是 101 ，此时的收敛速度为 \frac{2}{3} ， 在最坏情况下 ： 主分支上每次需要遍历的次数为 \sum\limits_{i=1}^{100} \frac{2}{3}^i \times n

所以发杂度较好

每层 0 / 1 数量统计

每一层 1 的数量是 上一层 1 的数量 + 上一层 0 的数量

每一层 0 的数量是 上一层 1 的数量

代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int lli;
const int N = 2e5 + 10;
lli total_ask, Length, Limit, Num1, Num2, Num3;
lli P = 998244353;
lli mod(lli num){
    return ((num % P) + P) % P;
}
vector<lli> one(200), zero(200);
lli solve(string put, int Len){
    if(put.size() == 1){
        lli num = put[0] - '0';
        if(num == 1) return one[Len];
        else return zero[Len];
    }
    string pre;
    if(put[0] == '0') pre += '1';
    for(int temp = 0 ; temp < put.size() - 1; temp++){
        if(put[temp] == '1'){
            if(put[temp + 1] == '0') pre += '1';
            else pre += '0';
        }else{
            if(put[temp + 1] == '0')
                return 0;
        }
    }
    lli new_Len = Len - 1;
    if(new_Len < 0) return 0;
    lli ans = 0;
    if(put[put.size() - 1] == '0') ans += solve(pre, new_Len);
    else{
        ans = mod(ans + mod(solve(pre + '0', new_Len)));
        ans = mod(ans + mod(solve(pre + '1', new_Len)));
    }
    return mod(ans);
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    one[0] = 0; zero[0] = 1;
    for(int temp = 1 ; temp <= 100 ; temp++){
        one[temp] = mod(zero[temp - 1] + one[temp - 1]);
        zero[temp] = mod(one[temp - 1]);
    }
    string put; lli deep;
    cin >> deep >> put;
    cout << solve(put, deep);
    return 0;
}