時(shí)間限制:C/C++ 1秒悔详,其他語言2秒
空間限制:C/C++ 262144K枉层,其他語言524288K
一闻察、題目?jī)?nèi)容
題目描述
定義一個(gè)數(shù)字為幸運(yùn)數(shù)字當(dāng)且僅當(dāng)它的所有數(shù)位都是4或者7纬纪。
比如說揍移,47览濒、744呆盖、4都是幸運(yùn)數(shù)字而5拖云、17、467都不是应又。
現(xiàn)在想知道在1...n的第k小的排列(permutation)中宙项,有多少個(gè)幸運(yùn)數(shù)字所在的位置的序號(hào)也是幸運(yùn)數(shù)字。
輸入描述
第一行兩個(gè)整數(shù)n株扛,k尤筐。
1 <= n,k <= 1000,000,000
輸出描述
一個(gè)數(shù)字表示答案洞就。
如果n沒有k個(gè)排列盆繁,輸出-1。
示例1
輸入
7 4
輸出
1
說明
第4小的排列:1 2 3 4 6 7 5
示例2
輸入
4 7
輸出
1
說明
2 1 3 4
二旬蟋、解題思路
依據(jù)題意:1油昂、幸運(yùn)數(shù)字為由4或7組成;2咖为、1~n的第k小排列秕狰;上述兩個(gè)條件成立成立即輸出數(shù)列中幸運(yùn)數(shù)字的位置序號(hào)也是幸運(yùn)數(shù)字的個(gè)數(shù)。
第一種條件躁染,我們直接逐一比較即可鸣哀。針對(duì)第二種條件,我們知道一個(gè)容量為n的數(shù)組全排列的所有可能性為n!種吞彤,題目中的k只有1e9我衬,因?yàn)?3!已經(jīng)大于1e9,所以即使n再大饰恕,會(huì)變的也只有后面的13位挠羔,前面的位置和數(shù)字都是一樣的。由此我們聯(lián)想到逆康托展開埋嵌。
康托展開相關(guān)概述:
舉個(gè)栗子破加,對(duì)于1~5的一個(gè)全排列[1,2,3,4,5]和[5,4,3,2,1],從字典序而言,前者是該全排列集的第一個(gè)雹嗦,后者是該集的最后一個(gè)范舀。那么康托展開,即給定一個(gè) n 位數(shù)的全排列了罪,我們可以根據(jù)康托展開公式確定其應(yīng)當(dāng)是字典序中的第“幾”個(gè)全排列锭环。
由于康托展開計(jì)算的是某個(gè)全排列方式在該全排列集合中的字典序,其映射關(guān)系唯一且單調(diào)泊藕,故該映射關(guān)系是可逆的辅辩。即,我們給定一個(gè)全排列的所有字符,以及某個(gè)字典序號(hào)玫锋,我們可以利用逆康托展開得到相應(yīng)的那個(gè)全排列蛾茉。
下圖為康托展開運(yùn)算公式,其中ai為整數(shù)景醇,且0 <= ai < i臀稚,1 <= i <= n;
康托展開運(yùn)算
康托展開
以[3,4,1,5,2](數(shù)組a)為例,計(jì)算他的康托展開值(字典序)
- 首位為3三痰,則小于3的數(shù)由兩個(gè)吧寺,為1、2散劫,a[5] = 2稚机,則首位小于3的所有排列組合為a[5] * (5 - 1)!
- 第二位為4,由于第一位小于4获搏,1赖条、2、3種一定會(huì)有1個(gè)充當(dāng)?shù)谝晃怀N酰虼伺旁?之下的只剩2個(gè)纬乍,所以其實(shí)計(jì)算的是在第二位之后小于4的個(gè)數(shù)。因此a[4] = 2裸卫;
- 第三位是1仿贬,則在其后小于1的數(shù)有0個(gè),因此a[3] = 0墓贿;
- 第四位是5茧泪,則在其后小于5的數(shù)有1個(gè),為2聋袋,因此a[2] = 1队伟;
- 最后一位,由于在它之后已經(jīng)沒有數(shù)了幽勒,因此a[1]固定為0嗜侮;
根據(jù)公式:
X = 2 * 4! + 2 * 3 ! + 0 * 2! + 1 * 1! + 0 * 0! = 61
因此比數(shù)組[3,4,1,5,2]小的組合有61個(gè)。
逆康托展開
這里我們用到逆康托展開啥容,以[3,4,1,5,2](數(shù)組a)為例棘钞。這里輸入和輸出互反,同時(shí)我們需要輸入全排列的字符個(gè)數(shù)n干毅。(以下用到數(shù)組a)
我們通過康托展開公式得到數(shù)組a的排位為:61
- 用 61 / 4! = 2余13,說明a[5] = 2泼返, 說明比首位小的數(shù)由2個(gè)硝逢,所以首位為3。
- 用 13 / 3! = 2余1,說明a[4] = 2渠鸽,說明在第二位之后小于第二位的數(shù)有2個(gè)叫乌,所以第二位為4。
- 用1 / 2! = 0余1徽缚,說明a[3] = 0憨奸,說明在第三位之后沒有小于第三位的數(shù),所以第三位為1凿试。
- 用 1 / 1! = 1余0排宰,說明a[2] = 1,說明在第四位之后小于第四位的數(shù)有1個(gè)那婉,所以第四位為5板甘。
- 最后一位自然數(shù)就是剩下的數(shù)2。
- 綜上所述详炬,所求的排列組合為[3,4,1,5,2]盐类。
因此在這里我們分為兩部分解決:
- 當(dāng)n<=13時(shí),因?yàn)榇嬖趉>n!呛谜,因此增加特殊判斷:如果k<n!在跳,那么我們可以用逆康托展開直接得到地k個(gè)序列,然后逐一判斷即可隐岛。
- 當(dāng)n>13時(shí)猫妙,從1~n-13都是位置和數(shù)字一樣,只有后面的13位會(huì)發(fā)生改變礼仗,同樣的我們使用逆康托展開運(yùn)算即可求出答案吐咳。
代碼實(shí)操
#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;
}