SSOJ1270数列（NOIP2006）
2272+
作者：crxis 发布：2019-06-12 分类：深度优先搜索
题目大意：一个序列中的元素为所有有限个互不相等的k的方幂之和，请问第n个是多少？
题目描述
给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
1，3，4，9，10，12，13，…
（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
请你求出这个序列的第N项的值（用10进制数表示）。
例如，对于k=3，N=100，正确答案应该是981。
输入
输入只有1行，为2个正整数，用一个空格隔开：
k N （k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。
输出
输出为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*109）。（整数前不要有空格和其他符号）。
样例输入
3 100
样例输出
981
提示
NOIP2006普及组第四题
解题思路
题目保证答案在int范围内，k最小是3，最极端的情况下，幂小于20，因为2^30超过int范围，不会用到。
也就是说，对于所有的k，其幂小于20。数据很小，我们可以暴力枚举每种幂选不选，最后选了的求和得到数字。全部存起来，排序输出第n个值就行。
注意：全不选是不行的，所以0这个值要排除；去重有很多种方法，其实不会有重复，如果不想证明那就写个去重。
程序实现
写完爆搜，很容易想到其实跟二进制有关。对于第x位，0表示不选，1表示选，选了的话加k^x；如果k=2，跟二进制的带权展开一样的，2^0+2^1+…+2^x = 2^(x+1) – 1 < 2 ^ (x+1)，对于更大的禁止，更加不会有重复。第n个，如果n的二进制是10001000，那么他就是k^7+k^3。
