题目描述
已知,$a_1,a_2,…,a_n$ 是$1∼n$的全排列中字典序第 k 个排列。请你判断,一共有多少个整数 x
同时满足以下所有条件:
1. $1≤x≤n$
2. x的十进制表示不含 4 和 7以外的数字。
3. $a_x$的十进制表示不含 4和 7以外的数字。
输入格式
共一行,包含两个整数 n,k。
输出格式
如果 1∼n的全排列中字典序第 k个排列根本不存在,则输出 -1。
否则,输出一个整数,表示满足条件的 x的数量。
数据范围
前 4个测试点满足 $1≤n,k≤10$。
所有测试点满足 $1≤n,k≤10^9$。
输入样例1:
7 4
输出样例1:
1
输入样例2:
4 7
输出样例2:
1
输入样例3:
3 7
输出样例3:
-1
题解:
我们发现n的范围非常大,直接暴力求解不现实。
因为三个条件同时处理非常困难,我们先考虑所有满足前两个条件的数。考虑到n不超过$10^9$,x的位数不超过9.当x为i位数时,满足前两个条件的x有$2^i$个(每一为可以有4,7两种选择)。所以一共有$2+2^2+2^3+ … +2^9=1022$个备选答案,可以直接用递归来枚举。接下来,我们的问题简化为:求n的全排列中字典序第 k 个排列中第x个数的值。首先这里需要一点康托展开的知识。我在这里也大致描述一下。我们先考虑n的全排列的第一位,当$k$小于等于$(n-1)!$时说明排列的第一位必须为1(后面n-1位的全排列已经有$(n-1)!$个数了)。当k大于$(n-1)!$时,说明排列的第一位大于1.我们将k减去$(n-1)!$,并将排列的第一位调大一个数,再次与$(n-1)!$比较,看是否需要再次调整。接着考虑第二位,我们将第一位留下的k值与$(n-2)!$进行类似比较,以此来确定第二位。依此类推,我们可以推得n的全排列中字典序第 k 个排列中任意一位数的值(注意每位取值要保证与前面数位不重复)。
我们以样例2($n = 4, k = 7$)为例展开说明:
1.考虑第一位:将排列的第一位设为1
但由于 3! < 7 ((n - 1)! < k)
k = k - 3! (k = k - (n-1)!)
k = 1,并将排列的第一位调为2
2.考虑第二位:将排列的第二位设为1
2! > 1 ((n - 2)! > k)
排列的第二位确定为1
3.考虑第三位: 将排列的第三位设为3(当前最小)
1! >= 1 排列的第三位确定为3
4.考虑第四位:确定为4
但这样任然行不通,因为n的范围过大($10^9$),直接操作会超时。但是k的范围也是$10^9$,我们算得$12! <10^9,13! > 10^9$。因此,我们只需要考虑最后的几位即可(前面数位保证$a_x = x$)。对于每一个备选答案,我们只需对最后的几位进行上述操作即可。
代码如下
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n, k, res;
bool vis[15];
int fac(int t){ //求x的阶乘
long long ans = 1;
for(int i = 1; i <= t; i++){
ans *= i;
if(ans > k)
return k + 1; //本题特殊处理,超过k的数我们不关注其具体值
}
return ans;
}
bool only47(int x){ //判断x中是否只含有4,7
while(x > 0){
int tmp = x % 10;
if(tmp != 4 && tmp != 7)
return false;
x /= 10;
}
return true;
}
int get_num(int pos){ //获取排列pos位置的值
int t = 0;
while(fac(t) <= k)
t++;
if(pos <= n - t)
return pos;
int rank = k;
memset(vis, 0, sizeof(vis));
for(int i = n - t + 1; i <= n; i++){
for(int j = 1; j <= t; j++){
if(vis[j]) continue;
if(rank <= fac(n - i)){
vis[j] = 1;
if(pos == i)
return j + n - t;
break;
}
rank -= fac(n - i);
}
}
return 0;
}
void dfs(long long pos){ //枚举备选答案
if(pos > n)
return;
if(pos > 0 && only47(get_num(pos)))
res++;
dfs(pos * 10 + 4);
dfs(pos * 10 + 7);
}
int main(){
scanf("%d%d", &n, &k);
if(fac(n) < k){
printf("-1\n");
return 0;
}
res = 0;
dfs(0);
printf("%d\n", res);
return 0;
}