《Biinary Numbers》题目分析

这道题是一道计数问题。我们一开始就会有一个大概的思路：依次确定每一个二进位是0、1还是2，分别计算3种情况下表示方法的数目。

我们下面介绍2种不同的方法，一种是从最高位到最低位依次计算，另一种是从最低位到最高位依次计算。

假设我们要求N=10的表示方法数，10的二进制表示是(1010)2，我们用f(1010)表示(1010)2在扩展二进制下有多少种表示方法。

如果我们用扩展二进制表示10，那么10的最高位(2^3这一位)有两种可能，一种是0，一种是1。

如果最高位是1，那么剩下3位我们只需要表示(010)2，表示方法一共有f(010)种。

如果最高位是0，那么剩下3位需要表示的数是(010)2再加上第四位(2^3)的1，我们用f(1|010)来表示用三位扩展二进制数表示(1010)2有多少种方法。

对于f(010)，我们考虑(010)2的最高位只有0一种可能，所以f(010)=f(10)。

对于f(1|010)，我们考虑第三位只可能是1或者2。如果是1，后2位表示方法有f(1|10)种；如果是2，后两位表示方法有f(10)种。

我们可以把上述N=10的计算的递归树的画出来，如下图：

我们写一个递归程序来实现以上的计算过程：

int f(int k, int rest) {  //递归计算f(rest|a[k..0])，其中rest是0/1,a[k..0]是n的二进制表示的后缀
        if(k == 0) {
                if(a[0] == 1 && rest == 1) return 0;
                else return 1;
        }
        int sum = a[k] + 2 * rest;
        if(sum == 3) return f(k-1, 1);
        if(sum == 2 || sum == 1) return f(k-1, 0) + f(k-1, 1);
        return f(k-1, 0);
}
int main()
{
        cin >> n;
        m = 0;
        while(n) {  //a[m-1] .. a[0]是n的二进制表示
                a[m] = n & 1;
                n >>= 1;
                m++;
        }
        cout << f(m-1, 0) << endl;
        return 0;
}

值得一提的是，上述递归算法有很多重复计算，例如橘色、灰色和绿色的函数值。不过它仍然能在时限内通过所有的数据，你能准确计算出上述递归算法的复杂度吗？

我们可以发现，每一层只有2个函数值要求：f(N的二进制表示的后缀)和f(1|N的二进制表示的后缀)。所以我们可以用动态规划来优化上述递归算法，保证每个函数值只被计算一次。复杂度O(logN)。

以上是从最高位向最低位依次确定每一位的值。我们还可以倒过来从最低位向最高位依次确定。可以得到一个更简单的递归算法：

int calc(int n) {
        if (n == 0) return 1;
        if (n % 2 == 0) return calc(n / 2) + calc(n / 2 - 1);
        return calc(n / 2);
}

int main() {
        int n;
        cin >> n;
        cout << calc(n) << endl;
        return 0;
}

具体推导留给大家思考。

最后我们介绍一个研究数列问题的大杀器https://oeis.org。OEIS是一个整数数列百科全书，你可以输入数列的连续若干项，OEIS会告诉你这些项可能是哪个数列的一部分。以及这个数列有什么性质、递归公式、通项公式等等。

比如这周的题目我们可以手算出来N=1~8的值分别是1,2,1,3,2,3,1,4。在OEIS中搜索1,2,1,3,2,3,1,4就可以知道这个数列的信息啦。