自动搬运

查看原文

来自洛谷，原作者为

	Harry_Hedwig 记住，霍格沃茨永远与你同在

搬运于2025-08-24 21:24:29，当前版本为作者最后更新于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 范围下能逆康托展开多少个数（骗多少分）。

$n$	阶乘结果
$1$
$2$
$3$	$6$
$4$	$24$
$5$	$120$
$6$	$720$
$7$	$5,040$
$8$	$40,320$
$9$	$362,880$
$10$	$3,628,800$
$11$	$39,916,800$
$12$	$479,001,600$
$13$	$6,227,020,800$

诶诶诶停停停，根据数据范围，$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$ 个数，剩余的数按序排列的话，我们就可以把幸运数给预处理出来。那么这个时候，我们就肯定需要开始找规律了。

$$4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,\dots $$

接着，你会发现只有一位的幸运数有 $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