《非法二进制数》题目分析
本题是一道动态规划题目。
阶段的划分比较明显，直接按照位数划分即可，换句话说我们要依次算出1位、2位、3位……非法二进制数的数目。
之后是状态的设计。有经验的同学能一步到位设计出合理的状态，我们这里介绍一种“缺啥补啥”的思路。
首先我们直接从问题出发，用f[i]表示i位非法二进制数的数目。然后我们想一想能不能用f[1], f[2] ... f[i-1]求出f[i]。
如果X的第i位是0，那么X是i位非法二进制数当且仅当X的前i-1位是个非法二进制数。
如果X的第i位是1，那么X是i位非法二进制数当且仅当以下2种情况：
- X的前i-1位是个非法二进制数
- X的前i-1位是个合法二进制数，并且X第i-1位是1
注意到以上两种情况是互斥的，所以我们只需对以上两种情况求和即可。
综合上面的讨论，可以发现我们要求f[i]，需要知道：
- i-1位非法二进制数的数目，这个我们已经知道是f[i-1]
- i-1位末位是1的合法二进制数数目，这个目前我们不知道
对于不知道的量我们就设个变量表示，比如用g[i]表示“i位二进制数中末位是1的合法二进制数数目”。这样我们的问题就变成了如何求g[i]。
假设Y是个i位二进制数中末位是1的合法二进制数。那么Y的前i-1位必须是个末位是0的合法二进制数。
我们用h[i]表示末位是0的i位合法二进制数的数目。考虑到h[i]应该是所有i位二进制数的数目(2^i)，减去非法二进制数的数目(f[i])，再减去合法二进制数中末位是1的二进制数(g[i])，所以h[i] = 2^i - f[i] - g[i]。
于是我们就有了边界条件：f[1] = 0, g[1] = 1, h[1] = 1
以及递推方程：
f[i] = f[i-1] * 2 + g[i-1]
g[i] = h[i-1]
h[i] = 2^i - f[i] - g[i]
最后在实现代码的时候需要注意对10^9+7取模。
以上就是我们“缺啥补啥”的设计状态的思路。当然本题还有很多不同的状态表示方法，大家可以多思考思考。
自动机也是个好方法