题目描述

难度分:$1547$

输入一个长度至多为$10^5+1$的二进制字符串$s$，不含前导零。

把$s$当作一个二进制数。输出有多少对非负整数$(a,b)$，满足$a+b \leq s$且$a+b=a \oplus b$。答案模$10^9+7$。

输入样例$1$

10

输出样例$1$

5

输入样例$2$

1111111111111111111

输出样例$2$

162261460

算法

动态规划

状态定义

$f[i][1]$表示$a+b$的二进制前$i$位恰好和$s$相同的方案数，$f[i][0]$表示严格小于$s$的方案数。两种情况算在一起就是$a+b \leq s$的所有集合，在这个定义下答案就是$f[n][0]+f[n][1]$，其中$n$是$s$的长度。

状态转移

考虑等于的情况：如果$s[i]=$1，那么恰好等于$s$的情况下$a$和$b$在这一位可以填$0,1$或$1,0$，一共两种方案，状态转移方程为$f[i][1]=f[i-1][1] \times 2$。如果$s[i]=$0，那么$a$和$b$在当前位就只能填$0,0$，只有一种方案，状态转移方程为$f[i][0]=f[i-1][0]$。

考虑小于的情况：如果前面已经保证小于$s$了，则当前位只要不进位怎么填都行，有$0,1$、$1,0$、$0,0$三种情况，状态转移方程为$f[i][0]=f[i-1][0] \times 3$。如果前面都是相等的（相当于数位DP时前面的位满足$islimit=$true），只有在$s[i]=$1时才有这种情况，此时只要在当前位填$0,0$即可，状态转移方程为$f[i][0]=f[i-1][0] \times 3+f[i-1][1]$。

初始情况下考虑$0$位$s=0$，$f[0][0]=0$不存在严格小于的情况，存在一种等于的情况$f[0][1]=1$。

复杂度分析

时间复杂度

遍历一遍字符串$s$就可以求得答案，而单次转移是$O(1)$的，所以整个算法的时间复杂度为$O(n)$。

空间复杂度

DP数组$f$是滚动实现的，因此除去输入的字符串$s$，仅使用了有限几个变量。整个算法的额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
string L;
int n;

int main() {
    cin >> L;
    n = L.size();
    int f0 = 0, f1 = 1;
    for(int i = 0; i < n; i++) {
        f0 = f0 * 3LL % MOD;
        if(L[i] == '1') {
            f0 = (f0 + f1) % MOD;
            f1 = f1 * 2LL % MOD;
        }
    }
    cout << (f0 + f1) % MOD << endl;
    return 0;
}