原题见这里
定义了一种新的数字表示方式Decibinary，看起来像极了十进制和二进制的结合。
每一位上的数字，可以是0~9，但是每一位对应值，是2的若干次方，例如Decibinary表示法的2016对应的实际数值计算如下：
- (2016) = 2 * 8 + 0 * 4 + 1 * 2 + 6 * 1 = 24(10进制)
但这种表示方式，有一个问题，那就是，可能有多个数对应同一个实际的数值，例如对于2008:
- (2008) = 2 * 8 + 0 * 4 + 0 * 2 + 8 * 1 = 24(10进制)
这样2016和2008对应的实际数值是一样的。
现在考虑将全部的Decibinary进行排序，排序规则如下：
- 按每个数对应的实际10进制数值从小到大排列。
- 如果多个数对应的10进制数相同，则把它们看作10进制数，从小到大排列。例如，上面的2008和2016，对应10进制数都是24，而看作10进制数的话，2008 < 2016，因此2008排在前面。
问题是，给定若干次查询，每个查询包含一个数字x，输出在排序好的Decibinary数字中第x个数字。
说实话，这道题我没有自己想出来。钻研的那几天由于感情问题，脑子不好使，有点无能为力，就直接看答案了。
其实应该说，我的方向没有错，知道应该怎样做，但是动态规划的函数想不出来了:-(
思路是这样的：
- 从小到大算出每个10进制数对应的Decibinary数有多少个（算到能覆盖查询范围内的最大值即可），并进行累加求和，这样，对于第x个数字，就能确定对应的10进制数字是多少了。 同时，也能得到它在此10进制数字对应的Decibinary数中的排序。
- 所以，再返回某个10进制数从小到大排序的Decibinary数对应位是哪个即可。
上面这两点，看着是要使用两个数组(函数)，但其实需要的只是一个动态规划函数即可。
令dp(d, s)表示10进制数值为s，写成Decibinary数后最多有d+1位的总数量。则：
- 若d = -1，则若s = 0，返回1，否则返回0。也就是，在没有位数时，只有0才是成立的。
- 否则，设result = 0, 对于i from 0 to 9:
- 令remain = s - i * (1 << d)。若remain小于0，继续遍历下一个i，否则转2.2
- result += dp(d-1. remain) 返回result。意思是，累加上，最高位分别取0, 1, 2, ... 9，对应值为s减去相应值时的总数量。
然后，每个10进制数i对应的Decibinary数就是dp(无穷大，i)了，当然，实际过程中不会真的算到无穷大的。
对于i来说，若2 ^ t > i且 2 ^(t-1) <= i，则写成Decibinary数的最多位数就是t位，因为t及更高位取1的话，值就比i大了，因此前面都只能是0。
那么，就可以慢慢尝试扩大范围，决定d和s的最大取值了，使得到s最大值为止，对应的Decibinary累加数量恰好超过x的最大取值范围即可。
最终我这边得出来一个还算可以的结果，s最大为285501，d最大为18。
那么，如何得到某个10进制数k从小到大排序的第j个Decibinary数是多少呢？其实还是基于dp函数的结果。
首先，可以决定对应的数有多少位，因为排序时，位数低的总是排在前面。那么，首个满足dp(u, k) >= j的u，就是最高位了。
然后，可以决定最高位要取多少，方法是同dp方法里的一样，从0开始到9，不断累加dp(d-1, remain)，第一个累加结果 >= j的，就是最高位对应的数了。
接下来，次高位怎么决定呢，既然已经知道了最高位，那么就能计算出剩余数值k'，同时也能算出后面取的数会在k'对应Decibinary数中的排序j'。
那就，跟上面一样，继续尝试对次高位从0到9遍历，不断累加dp，找到第一个累加结果 >= j'的u'，再继续更新剩余数值和对应排序。
依此类推迭代，就能求出每一位了。当然，实际求的过程中还有一点可以优化，那就是如果迭代到了k' = 0，则必然后面所有位都取0了。
具体代码见solve.php