CodeForces - 121C 康托展开

题目链接：http://codeforces.com/problemset/problem/121/C

题目大意：

给你一个长度为n，字典序为k的排列。问：这个排列在幸运数字位置为幸运数字的数字有多少个。

幸运数字：每位只有4或者7。

n， k < 1e9。

对于k，我们知道只有最后13位变化。前面可以直接统计，后来用康托展开+暴力统计。

#include <bits/stdc++.h>
using namespace std;

long long fac[25]={1};
long long val[25];
bool vis[25];
vector<long long> v;
map<long long , long long> st;

void reverse_contor(long long n, long long x){
    memset(vis,0,sizeof vis);
    x--;
    long long j;
    for(long long i=1;i<=n;i++){
        long long t=x/fac[n-i];
        for(j=1;j<=n;j++){
            if(!vis[j]){
                if(!t) break;
                t--;
            }
        }
        v.push_back(j);
        vis[j]=1;
        x%=fac[n-i];
    }
}

long long ans=1;
long long dfs(long long i, long long n, long long s){

    if(i==n){
        st[s]=ans;
        ans++;
        return 0;
    }
    dfs(i+1, n, s*10+4);
    dfs(i+1, n, s*10+7);
}

long long chcke(long long n){
    while(n){
        if(n%10!=4&&n%10!=7){
            return 0;
        }
        n/=10;
    }
    return 1;
}

int main(){

    for(long long i=1;i<=13;i++) fac[i]=fac[i-1]*i;
    long long n, k, s=0;
    scanf("%lld%lld",&n, &k);

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

    for(long long i=1; i<=10; i++){
        dfs(0, i, 0);
    }

    if(n>13){
        pair<long long, long long> p=*st.lower_bound(n-13);
        s=p.second;
        if(p.first!=n-13){
            s--;
        }

    }else{
        reverse_contor(n, k);
        for(long long i=0; i<v.size(); i++){
            if(chcke(i+1)&&chcke(v[i])){
                s++;
            }
        }
        printf("%lld\n", s);
        return 0;
    }

    reverse_contor(13, k);
    for(long long i=0; i<v.size(); i++){


        if(chcke(i+1+n-13)&&chcke(v[i]+n-13)){
            s++;
        }
    }
    printf("%lld\n", s);

    return 0;
}