P1384 幸运数与排列 题解

Harry_Hedwig · 2022-01-27 21:02:02 · 题解

先看题。

0x00 思路

一个数是幸运数当且仅当这个数仅由 4 和 7 构成，比如 47，744，4747。

询问在1 到 n 的全排列中字典序第 k 小的排列中，有多少个幸运数在排列中的位置编号也是幸运数。

我们注意到，在完成对幸运数记数的问题前，我们首先对这个数列有一个逆康托展开，所以这个问题可以分成两步走。

0x01 Step 1：逆康托展开

很明显，逆康托展开就是个板子，所以直接开开森森打代码就好了。

但是，逆康托展开需要知道 n!，而数据范围告诉我们：1 \leq n,k\le 10^9。

！这…… unsigned long long 都存不下啊……高精度？也感觉不对。

现在我们的思路卡住了，所以我们可以碰碰运气，看在 unsigned long long 范围下能逆康托展开多少个数（骗多少分）。

诶诶诶停停停，根据数据范围，k 的取值范围是 1\sim 10^9，而 13!=6,227,020,800>10^9，所以我们可以发现 k 只会影响到数列的后 13 位，而前面的数都是按序排列！也就是说，我们只需要对最后 13 位执行全排列操作。

而关于 -1，只需要判断 n!<k 是否无解，为了偷懒不搞特殊，可以将 n 和 13 取最小值可以少写一个 if 语句。

至此，第一步顺利解决了。

0x02 Step 2：幸运数

既然我们已经发现除开最后 13 个数，剩余的数按序排列的话，我们就可以把幸运数给预处理出来。那么这个时候，我们就肯定需要开始找规律了。

接着，你会发现只有一位的幸运数有 2 个，两位数的有 4 个，三位数的有 8 个，…，n 位的幸运数有 2^n 个。

这个事情解释起来很简单。我们可以把 n 位拆成前面一位和后 n-1 位， n-1 也可以这样操作，而每一位都有两种选择：4 和 7，而每一位的选择都会影响到这个数，因此有 2^n 种可能，之后可进行预处理。

由于整个数列只有后 13 位会变化，所以前面的不会影响到第 k(1\le k \le n) 位的最大幸运数的数字总数可以直接相加。

注意！

当 10\le n< 20 时， 后 13 位中包括了个位数的幸运数，那么此时我们不可以再直接让答案为 2，而需要一个个判断（毕竟就 2 个幸运数）。

当 17\le n 时，幸运数 4 不会受影响。

当 20\le n 时，幸运数 7 不会受影响，可以分别判断。

但是千万不要忘了 n>20 的情况已经加过了，千万不要重加！

关于和 n 位数（有 dig 位）相同但小于 n-13 的幸运数，可以直接暴力查找，反正数量最多也就 2^9。从 44\dots4（dig 个 4）开始。可以根据幸运数特点，只有 4 和 7，可以推断出：找到幸运数中的第一个 4，将其变成 7，在这一位之前的 7（即从个位开始连续的所有 7) 全部改成 4 。

特别地，77\dots7（dig 个 7）为 dig 位的最大幸运数。

最后还有被全排列过的 13 位（至多）需要判断。前面的全排列已经在 Step 1 中得到了，直接判断位置和数值是否均为幸运数即可。

Code

#include<bits/stdc++.h>
using namespace std;
long long val_fac[20],val_pow[10];
long long step_1[20];
void decontor(int n,int p)//逆康托展开
{
    vector<int>mus,ans;
    int now=p-1,i;
    for(i=1;i<=n;i++)
        mus.push_back(i);
    for(i=n;i>=1;i--)
    {
        int l=now/val_fac[i-1];
        now=now%val_fac[i-1];
        ans.push_back(mus[l]);
        mus.erase(mus.begin()+l);
    }
    for(i=0;i<n;i++)
        step_1[i+1]=ans[i];
}
int Digit(int num)//找位数
{
    int sum=0;
    while(num)
    {
        num/=10;
        sum++;
    }
    return sum;
}
void change(long long &n)//改成下一个幸运数
{
    long long ans=n;
    int sum=0;
    while(ans%10==7)//即上文说的找法
    {
        ans/=10;
        n-=3*(int)pow(10,sum);
        sum++;
    }
    n+=3*(int)pow(10,sum);
}
bool check(int val)//检查是否满足幸运数的条件
{
    while(val)
    {
        if(val%10!=4&&val%10!=7)
            return 0;
        val/=10;
    }
    return 1;
}
int main()
{
    int p,i,n;
    long long ans=0;
    scanf("%d %d",&n,&p);
    val_fac[0]=1;
    val_pow[0]=1;
    for(i=1;i<=15;i++)//逆康托展开前置
        val_fac[i]=val_fac[i-1]*i;
    int dig=Digit(n);//求位数
    for(i=1;i<=dig;i++)//预处理
        val_pow[i]=val_pow[i-1]*2;
    if(p>val_fac[min(n,13)])//判断-1
    {
        printf("-1");
        return 0;
    }
    decontor(min(n,13)/*最多13位,否则就不行了*/,p);
    if(n>13)
    {
        if(n>19)//不会影响到任何低于dig位的幸运数
            for(i=1;i<dig;i++)
                ans+=val_pow[i];
        if(n>16&&n<20)//会影响到7
            ans++;
        for(i=1;i<=13;i++)//在逆康托展开中使用的是1~13，需要加回来
            step_1[i]=step_1[i]+n-13;
        long long now=0,biggest=0;
        for(i=1;i<=dig;i++)//找到dig位的幸运数的最小值和最大值
            now*=10,now+=4,biggest*=10,biggest+=7;
        if(n-13>=biggest)//不会影响到dig位的所有幸运数
            ans+=val_pow[dig],now=n-12/*防止进入循环*/;
        while(now<=n-13&&now!=biggest)
        {
            ans++;
            change(now);
        }
        if(now<=n-13&&now==biggest)
            ans++;
        for(i=1;i<=13;i++)//暴力查找
        {
            if(check(n+i-13)&&check(step_1[i]))
                ans++;
        }
    }
    else
    {
        if(step_1[4]==4||step_1[4]==7)
            ans++;
        if(step_1[7]==4||step_1[7]==7)
            ans++;
    }
    printf("%lld",ans);
    return 0;
}

话说康托展开太容易打错了QaQ