题目链接：https://vjudge.net/problem/51Nod-1635
题解：这题是这学期最后一次模拟赛的A题：
题目大意就是说1到n的第m个全排列中，求下标和数值都是幸运数的个数，其中数字全是4或者7的数叫做幸运数。
刚开始想了好久，其实跟上次那题全排列类似，前面的数不受影响，可以用深搜判断，因为下标就等于数值，不需要一一分类讨论，第ii项开始，会因为第m个全排列而发生变化，所以要用for循环遍历一遍，当下标和数组的值都是幸运数，再让ans 。
总体思路挺简单的，判断是否幸运数的函数也不难写，中间的全排列产生如果看不懂，可以参考我以前写的博客。
把答案分为两部分，第一部分为1到ii-1不会变的数，第二部分为ii到n会变的数，一个深搜，一个遍历。
直接上代码：
代码语言：javascript复制#include<iostream>
using namespace std;
long long n, m, ans, a[100], f[100], g[100], n1;
long long pd(long long t){//a数组用于判断是否为幸运数
long long n1 = 0;
while (t){
n1 ;
a[n1] = t % 10;
t /= 10;
if (a[n1] != 4 && a[n1] != 7)return 0;
}
return 1;
}
void dfs(long long x) {//dfs深搜
if (x > n1)return;
if (x)ans ;
dfs(x * 10 4);
dfs(x * 10 7);
}
int main() {
long long i, ii, j, t, k, s, la;
scanf("%lld%lld", &n, &m);//1到n的第k个排列
t = 1;
for (i = 2; i <= n; i ) { //这里计算n的阶乘
if (t > m)break; //用于计算第m种排列会影响最后多少个数字
t *= i;
la = i;
}
if (t < m) { //如果n的阶乘比m小，输出-1
printf("-1");
return 0;
}
ii = la;//ii是受影响的最后数字的总排列个数
k = t;//k是受影响的最后数字的总排列阶乘
for (i = 1; i <= ii; i ){
g[i] = 1;
}
for (i = n - ii 1; i <= n; i ){ //最后ii 1个数遍历一遍
k /= (ii - (i - (n - ii 1)));//相当于n！除以n
s = 0;
for (j = 1; j <= ii; j ){
if (g[j]){
s ;
if (s * k >= m){
m -= (s - 1) * k;
g[j] = 0;
f[i - (n - ii)] = j (n - ii);
break;
}
}
}
}//实现第m个全排列
//全排列产生方法不会的看这里https://blog.csdn.net/qq_41464123/article/details/80584899
n1 = n - ii; //n1代表全排列中前面不变的数的个数
dfs(0); //0到n1是不会变的 所以直接暴力模拟
for (i = 1; i <= ii; i )//显然，ii是第m个排列影响到的最后几位的位数，
//会根据m的排列而变化 所以要判断下标和数值
if (pd(f[i]) && pd(n - ii i))ans ;
printf("%lldn", ans);//最后输出两部分的和
}
