算法

(数位Dp) $O(\log^2n)$

这个题的状态设计特别神奇，我们建立数组$f$表示：二进制表示有i位，且没有前导0的数的数量。
显然$f[i][j] = C_{i - 1}^j$。
重点在于如何快速求出1到n中圆形数字的数量。
假设n的二进制表示有m位，容易处理出m-1位及以下位数的数中圆形数字的数量，枚举0的个数套f的公式即可。
重点是求m位圆形数字的数量。
我们采用试填法。如果是最高位，直接跳过(没有前导0)；否则如果该位是1，则试填0，转化成套公式的问题；继续向下试填，直到穷举结束。
但是我们还发现，0还没有被算过，所以要加上0。
y总在提高课上说要特判0，但是本题由于特殊，没有特判，降低了编程的复杂度。
另外我在代码中为了节省空间，没有实现f数组，只实现了组合数的求法，具体见代码。
算法复杂度为：时间$O(log^2n)$，空间$O(log^2n)$，是一个比较优秀的算法。

总结

之前做这个题目的时候，搞了很长时间，还是WA。其实尝试不同的状态表示，或许就可以找到方法。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 40

using namespace std;

int a, b;
int c[maxn][maxn];

int dp(int n)
{
    vector<int> nums;
    while (n) nums.push_back(n % 2), n /= 2;
    int cnt = (nums.size() + 1) / 2;
    int res = 0, last = 0;

    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        if (i == nums.size() - 1) continue;
        int x = nums[i];
        if (x == 1)
        {
            for (int j = max(cnt - (last + 1), 0); j <= i; j ++ ) res += c[i][j];
        }
        else last ++ ;

        if (!i && last >= cnt) res ++ ;
    }

    for (int i = 1; i < nums.size(); i ++ )
    {
        cnt = (i + 1) / 2;
        for (int j = cnt; j < i; j ++ ) res += c[i - 1][j];
    }

    return res + 1;
}

int main()
{
    for (int i = 0; i < maxn; i ++ )
    {
        c[i][0] = 1;
        for (int j = 1; j <= i; j ++ ) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }

    scanf("%d%d", &a, &b);
    printf("%d\n", dp(b) - dp(a - 1));

    return 0;
}