簡(jiǎn)單排序——幸運(yùn)數(shù)字(康托展開)

時(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ì)算他的康托展開值(字典序)

  1. 首位為3三痰,則小于3的數(shù)由兩個(gè)吧寺,為1、2散劫,a[5] = 2稚机,則首位小于3的所有排列組合為a[5] * (5 - 1)!
  2. 第二位為4,由于第一位小于4获搏,1赖条、2、3種一定會(huì)有1個(gè)充當(dāng)?shù)谝晃怀N酰虼伺旁?之下的只剩2個(gè)纬乍,所以其實(shí)計(jì)算的是在第二位之后小于4的個(gè)數(shù)。因此a[4] = 2裸卫;
  3. 第三位是1仿贬,則在其后小于1的數(shù)有0個(gè),因此a[3] = 0墓贿;
  4. 第四位是5茧泪,則在其后小于5的數(shù)有1個(gè),為2聋袋,因此a[2] = 1队伟;
  5. 最后一位,由于在它之后已經(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

  1. 用 61 / 4! = 2余13,說明a[5] = 2泼返, 說明比首位小的數(shù)由2個(gè)硝逢,所以首位為3。
  2. 用 13 / 3! = 2余1,說明a[4] = 2渠鸽,說明在第二位之后小于第二位的數(shù)有2個(gè)叫乌,所以第二位為4。
  3. 用1 / 2! = 0余1徽缚,說明a[3] = 0憨奸,說明在第三位之后沒有小于第三位的數(shù),所以第三位為1凿试。
  4. 用 1 / 1! = 1余0排宰,說明a[2] = 1,說明在第四位之后小于第四位的數(shù)有1個(gè)那婉,所以第四位為5板甘。
  5. 最后一位自然數(shù)就是剩下的數(shù)2。
  6. 綜上所述详炬,所求的排列組合為[3,4,1,5,2]盐类。
因此在這里我們分為兩部分解決:
  1. 當(dāng)n<=13時(shí),因?yàn)榇嬖趉>n!呛谜,因此增加特殊判斷:如果k<n!在跳,那么我們可以用逆康托展開直接得到地k個(gè)序列,然后逐一判斷即可隐岛。
  2. 當(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;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市元践,隨后出現(xiàn)的幾起案子韭脊,更是在濱河造成了極大的恐慌,老刑警劉巖单旁,帶你破解...
    沈念sama閱讀 218,451評(píng)論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件沪羔,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡象浑,警方通過查閱死者的電腦和手機(jī)蔫饰,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,172評(píng)論 3 394
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來愉豺,“玉大人篓吁,你說我怎么就攤上這事◎嚼梗” “怎么了杖剪?”我有些...
    開封第一講書人閱讀 164,782評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵冻押,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我盛嘿,道長(zhǎng)洛巢,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,709評(píng)論 1 294
  • 正文 為了忘掉前任次兆,我火速辦了婚禮稿茉,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘芥炭。我一直安慰自己漓库,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,733評(píng)論 6 392
  • 文/花漫 我一把揭開白布蚤认。 她就那樣靜靜地躺著米苹,像睡著了一般。 火紅的嫁衣襯著肌膚如雪砰琢。 梳的紋絲不亂的頭發(fā)上蘸嘶,一...
    開封第一講書人閱讀 51,578評(píng)論 1 305
  • 那天,我揣著相機(jī)與錄音陪汽,去河邊找鬼训唱。 笑死,一個(gè)胖子當(dāng)著我的面吹牛挚冤,可吹牛的內(nèi)容都是我干的况增。 我是一名探鬼主播,決...
    沈念sama閱讀 40,320評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼训挡,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼澳骤!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起澜薄,我...
    開封第一講書人閱讀 39,241評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤为肮,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后肤京,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體颊艳,經(jīng)...
    沈念sama閱讀 45,686評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,878評(píng)論 3 336
  • 正文 我和宋清朗相戀三年忘分,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了棋枕。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,992評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡妒峦,死狀恐怖重斑,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情肯骇,我是刑警寧澤绸狐,帶...
    沈念sama閱讀 35,715評(píng)論 5 346
  • 正文 年R本政府宣布卤恳,位于F島的核電站,受9級(jí)特大地震影響寒矿,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜若债,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,336評(píng)論 3 330
  • 文/蒙蒙 一符相、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧蠢琳,春花似錦啊终、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,912評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至泰讽,卻和暖如春例衍,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背已卸。 一陣腳步聲響...
    開封第一講書人閱讀 33,040評(píng)論 1 270
  • 我被黑心中介騙來泰國(guó)打工佛玄, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人累澡。 一個(gè)月前我還...
    沈念sama閱讀 48,173評(píng)論 3 370
  • 正文 我出身青樓梦抢,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親愧哟。 傳聞我的和親對(duì)象是個(gè)殘疾皇子奥吩,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,947評(píng)論 2 355