AcWing 5052. 排列
原题链接
困难
作者:
氘ba-wt
,
2023-07-15 22:58:26
,
所有人可见
,
阅读 149
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
LL jiecheng[20];
int last[20];
bool check(int x){
while(x){
if(x % 10 != 4 && x % 10 != 7) return false;
x /= 10;
}
return true;
}
int main() {
int n, K;
cin >> n >> K;
bool flg = false;
LL s = 1;
for(int i = n; i >= 1; i--){
s *= i;
if(s >= K){
flg = true;
break;
}
}
if(flg == false){
puts("-1");
return 0;
}//全部的排列数不能达到K,则-1
jiecheng[1] = 1;
int len;
for(len = 2; jiecheng[len - 1] * len < K; len++){
jiecheng[len] = jiecheng[len - 1] * len;
}
jiecheng[len] = jiecheng[len - 1] * len;
//计算可能需要用到的阶乘数据,直到大于等于K
//len就是涉及的末尾可能变换的位置长度
int p = n - len + 1;//不变和变的临界点
set<int> ss;
for(int i = p; i <= n; i++){
ss.insert(i);
} //末尾len个数全部加入ss
for(int i = p, j = len; i <= n; i++, j--){
int shang = K / jiecheng[j - 1];
if(K % jiecheng[j - 1]) shang++;
int u = 0, v;
for(int x : ss){
if(++u == shang){
v = x;
break;
}
}
last[i - p] = v; //该位确定
ss.erase(v);
K %= jiecheng[j - 1];
if(K == 0){ //已经无数,则倒序放入
int r = n - p;
for(int x : ss){
last[r--] = x;
}
break;
}
}
//因为K在10^9范围内,所以涉及最多末尾12-13位
//将最后len位逐位逼近生成
int ans = 0;
queue<LL> q; q.push(4), q.push(7);
while(q.size()){
LL x = q.front(); q.pop();
if(x < p){
ans++;
q.push(x * 10 + 4);
q.push(x * 10 + 7);
}
}
//比p位低的位置,如果是只有4或7组成的,都是原数字没变
//利用队列生成判断,注意可能产生LL
for(int i = 0; i < len; i++){
int x = p + i;
if(check(x) && check(last[i])) ans++;
}
//最后len位判断该位置和值是否只有4或7组成
cout << ans << endl;
return 0;
}