启示录（二分+数位dp）

启示录（二分+数位dp）"/>

启示录（二分+数位dp）

古代人认为666是属于魔鬼的数。

不但如此，只要某数字的十进制表示中有三个连续的6，古代人也认为这是个魔鬼的数，比如666,1666,6663,16666,6660666等等。

古代典籍中经常用“第X小的魔鬼的数”来指代这些数，这给研究人员带来了极大的不便。

现在请编写一个程序，可以实现输入X，输出对应的魔鬼数。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组测试数据占一行，包含一个整数X。

输出格式

每组测试数据占一行，输出一个魔鬼数。

数据范围

1≤T≤1000,
1≤X≤5∗107

输入样例：

3
2
3
187

输出样例：

1666
2666
66666

思路：（二分+数位dp） 

首先，总体上就是二分1-1<<63-1中第一个包含的魔鬼数个数=x的数，即：个数=x且最小的数即为第x个魔鬼数；

在二分的判断条件中，要找当前数包含的魔鬼数个数，这里可以采用容斥原理+数位dp统计，即：

当前数n包含的魔鬼数个数 = 当前数包含的数(1-n)的总数n - n包含的数中的非魔鬼数个数

然后用数位dp统计n包含的数中的非魔鬼数个数即可。

现学了一下数位dp，大体理解了其模板，总结一下，我认为就是：