时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
一、题目内容
题目描述
定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。
比如说，47、744、4都是幸运数字而5、17、467都不是。
现在想知道在1...n的第k小的排列（permutation)中，有多少个幸运数字所在的位置的序号也是幸运数字。
输入描述
第一行两个整数n，k。
1 <= n，k <= 1000,000,000
输出描述
一个数字表示答案。
如果n没有k个排列，输出-1。
示例1
输入
7 4
输出
1
说明
第4小的排列：1 2 3 4 6 7 5
示例2
输入
4 7
输出
1
说明
2 1 3 4
二、解题思路
依据题意：1、幸运数字为由4或7组成；2、1～n的第k小排列；上述两个条件成立成立即输出数列中幸运数字的位置序号也是幸运数字的个数。
第一种条件，我们直接逐一比较即可。针对第二种条件，我们知道一个容量为n的数组全排列的所有可能性为n!种，题目中的k只有1e9，因为13!已经大于1e9，所以即使n再大，会变的也只有后面的13位，前面的位置和数字都是一样的。由此我们联想到逆康托展开。
康托展开相关概述：
举个栗子，对于1～5的一个全排列[1,2,3,4,5]和[5,4,3,2,1],从字典序而言，前者是该全排列集的第一个，后者是该集的最后一个。那么康托展开，即给定一个 n 位数的全排列，我们可以根据康托展开公式确定其应当是字典序中的第“几”个全排列。
由于康托展开计算的是某个全排列方式在该全排列集合中的字典序，其映射关系唯一且单调，故该映射关系是可逆的。即，我们给定一个全排列的所有字符，以及某个字典序号，我们可以利用逆康托展开得到相应的那个全排列。
下图为康托展开运算公式，其中ai为整数，且0 <= ai < i，1 <= i <= n;
康托展开运算
康托展开
以[3,4,1,5,2]（数组a）为例，计算他的康托展开值（字典序）
- 首位为3，则小于3的数由两个，为1、2，a[5] = 2，则首位小于3的所有排列组合为a[5] * (5 - 1)!
- 第二位为4，由于第一位小于4，1、2、3种一定会有1个充当第一位，因此排在4之下的只剩2个，所以其实计算的是在第二位之后小于4的个数。因此a[4] = 2；
- 第三位是1，则在其后小于1的数有0个，因此a[3] = 0；
- 第四位是5，则在其后小于5的数有1个，为2，因此a[2] = 1；
- 最后一位，由于在它之后已经没有数了，因此a[1]固定为0；
根据公式：
X = 2 * 4! + 2 * 3 ! + 0 * 2! + 1 * 1! + 0 * 0! = 61
因此比数组[3,4,1,5,2]小的组合有61个。
逆康托展开
这里我们用到逆康托展开，以[3,4,1,5,2]（数组a）为例。这里输入和输出互反，同时我们需要输入全排列的字符个数n。（以下用到数组a）
我们通过康托展开公式得到数组a的排位为：61
- 用 61 / 4! = 2余13，说明a[5] = 2， 说明比首位小的数由2个，所以首位为3。
- 用 13 / 3! = 2余1，说明a[4] = 2，说明在第二位之后小于第二位的数有2个，所以第二位为4。
- 用1 / 2! = 0余1，说明a[3] = 0，说明在第三位之后没有小于第三位的数，所以第三位为1。
- 用 1 / 1! = 1余0，说明a[2] = 1，说明在第四位之后小于第四位的数有1个，所以第四位为5。
- 最后一位自然数就是剩下的数2。
- 综上所述，所求的排列组合为[3,4,1,5,2]。
因此在这里我们分为两部分解决：
- 当n<=13时，因为存在k>n!，因此增加特殊判断：如果k<n!，那么我们可以用逆康托展开直接得到地k个序列，然后逐一判断即可。
- 当n>13时，从1～n-13都是位置和数字一样，只有后面的13位会发生改变，同样的我们使用逆康托展开运算即可求出答案。
代码实操
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
LL f[20];
int n,m,s;
void init() {
LL I;
f[0] = 1;
for(i = 1; i < 15; i++) {
f[i] = f[i - 1] * I;
}
}
int check(int x) {
while(x) {
if (x % 10 != 4 && x % 10 != 7)
return 0;
x = x / 10;
}
return 1;
}
void dfs(LL x, LL y) {
if (x > y)
return;
if (x != 0)
s++;
dfs(x * 10 + 4, y);
dfs(x * 10 + 7, y);
}
int solve(int x, int y) {
vector<int> p;
vector<int> q;
int i, j, k;
for(i = y; i <= n; i++) {
p.push_back(i);
}
for(i = n - y + 1; i >= 1; i--) {
j = x % f[i - 1];
k = x / f[i - 1];
x = j;
q.push_back(p[k]);
p.erase(p.begin() + k);
}
k = q.size();
j = 0;
for(i = 0; i < k; i++) {
if (check(q[i]) && check(i + y)) {
j++;
}
}
return j;
}
int main() {
int i, j, ans;
init();
scanf("%d%d",&n,&m);
if (n < 15 && f[n] < m) {
printf("-1\n");
return 0;
}
m--;
ans = 0;
s = 0;
if (n >= 15) {
dfs(0, n - 14);
ans += s;
ans += solve(m, n - 14);
} else {
ans = solve(m, 1);
}
printf("%d\n",ans);
return 0;
}
