P1384 幸运数与排列

神奇的（逆）康托展开：求1到n的全排列中字典序第k小的排列

$k<=10^9<13!$，显然$k$最多只会影响后$13$位

前面一大串都是有序从小到大排列的，于是搞个数位dp

后面一小串用逆康托展开求出原串，枚举是否符合条件。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

long long fac[]={,,,,,,,,,,,,,};

int n,k,x,e[],a[];

vector <int> p1,p2;

int dfs(int d,int w,int z){//普通的数位dp

    if(!d) return !z;

    if(!w&&!z&&e[d]>-) return e[d];

    int lim=w?a[d]:,tot=;

    for(int i=;i<=lim;++i)

        if(i==||i==||(z&&!i))

            tot+=dfs(d-,w&&(i==lim),z&&!i);

    if(!w&&!z) e[d]=tot;

    return tot;

}

int solve1(int A){

    int t=;

    while(A) a[++t]=A%,A/=;

    return dfs(t,,);

}

bool is(int x){

    for(;x;x/=) if(x%!=&&x%!=) return ;

    return ;

}

int solve2(){

    --k;

    for(int i=n-x+;i<=n;++i) p1.push_back(i);

    for(int i=x,v;i>=;--i){//逆康托展开求原串

        v=k/fac[i-]; k%=fac[i-];

        sort(p1.begin(),p1.end());

        p2.push_back(p1[v]);

        p1.erase(p1.begin()+v);

    }int tot=;

    for(int i=;i<x;++i)

        if(is(n-x+i+)&&is(p2[i])) ++tot;

    return tot;

}

int main(){

    scanf("%d%d",&n,&k);

    if(n<&&k>fac[n]){printf("-1");return ;}

    while(k>fac[x])++x;

    memset(e,-,sizeof(e));

    printf("%d",solve1(n-x)+solve2());

    return ;

}