主包也是被坑惨了，这题写了3个多小时. . .
首先第一眼看过去，这不就是一道 找规律 数学题吗。嗯，规律确实找到了，只不过不对而已(☆-ｖ-). . .但凡样例稍微大一点我都不用调那么久。
最开始想到的是：求出
≤n 的第一个
2k。实际上这个算法没有任何正确性可言. . .
一个反例：
n=8 时的拆分方案，我们想到的就是：
{8}
{4, 4}
{2, 2, 4}
{2, 2, 2, 2}
{1, 1, 2, 2, 2}
{1, 1, 1, 1, 2, 2}
{1, 1, 1, 1, 1, 1, 2}
{1, 1, 1, 1, 1, 1, 1, 1}
实际上还有两种：
{1, 1, 2, 4} 和
{1, 1, 1, 1, 4}
就这么轻轻松松的推翻了我们的猜想。然后问题就来了，知道哪儿错了以后怎么改呢？
完全背包
首先我们来转化一下问题：用无限多个面额
2t（t=0..k） 的“硬币”凑出总额
2k，统计不同的非负解（每种面额可用
0、1、2... 次）。这就是经典的完全背包。
为什么可以转化成这样呢？
n为
2的幂次时，这样转化当然成立。为什么
n 不为
2 的幂次时也成立呢？举个例子：
n=4→ 最小单位：
4根长度为
1的木棍
n=12→ 最小单位：
4根长度为
3的木棍
我们发现这没有什么区别，也就是说
n=4和
n=12其实是等价的。
这是纯dp的写法
总长是i的方案个数dpi=⎩⎨⎧包含长度1的木棍:去掉一根长度为1的木棍，对应dpi−1不包含长度1的木棍:仅使用长度为2，4，8，...2t的木棍凑出i →仅使用长度为1，2，4，...2t−1的木棍凑出2i
这题看上去挺麻烦的，需要算
k 以内有多少数码不包含
4 的数，实际上有一个小技巧可以处理：进制映射。
不包含
4 的数其实就是由
{0,1,2,3,5,6,7,8,9} 组成的数，我们将其看成九进制，映射为
{0,1,2,3,4,5,6,7,8}，这样每个数转化成十进制后就是不含
4 的数了。
举个例子：
(14365)映射=(15376)9=(5+1)×90+(6+1)×91+3×92+(4+1)×93+1×94=(10332)10
确实没有包含
4，所以序列中第
k 个数就是
k 映射后的结果。
练习题：
样例：
Input
CPP6
1
2
3
4
5
6
Output
CPPA
B
C
E
F
AA
U622716