题目链接：https://vjudge.net/problem/51Nod-1635
题解：这题是这学期最后一次模拟赛的A题：
题目大意就是说1到n的第m个全排列中，求下标和数值都是幸运数的个数，其中数字全是4或者7的数叫做幸运数。
刚开始想了好久，其实跟上次那题全排列类似，前面的数不受影响，可以用深搜判断，因为下标就等于数值，不需要一一分类讨论，第ii项开始，会因为第m个全排列而发生变化，所以要用for循环遍历一遍，当下标和数组的值都是幸运数，再让ans++。
总体思路挺简单的，判断是否幸运数的函数也不难写，中间的全排列产生如果看不懂，可以参考我以前写的博客。
把答案分为两部分，第一部分为1到ii-1不会变的数，第二部分为ii到n会变的数，一个深搜，一个遍历。
直接上代码：
1. #include<iostream> 2. using namespace std; 3. 4. long long n, m, ans, a[100], f[100], g[100], n1; 5. long long pd(long long t){//a数组用于判断是否为幸运数 6. long long n1 = 0; 7. while (t){ 8. n1++; 9. a[n1] = t % 10; 10. t /= 10; 11. if (a[n1] != 4 && a[n1] != 7)return 0; 12. } 13. return 1; 14. } 15. void dfs(long long x) {//dfs深搜 16. if (x > n1)return; 17. if (x)ans++; 18. dfs(x * 10 + 4); 19. dfs(x * 10 + 7); 20. } 21. int main() { 22. long long i, ii, j, t, k, s, la; 23. scanf("%lld%lld", &n, &m);//1到n的第k个排列 24. t = 1; 25. for (i = 2; i <= n; i++) { //这里计算n的阶乘 26. if (t > m)break; //用于计算第m种排列会影响最后多少个数字 27. t *= i; 28. la = i; 29. } 30. if (t < m) { //如果n的阶乘比m小，输出-1 31. printf("-1"); 32. return 0; 33. } 34. ii = la;//ii是受影响的最后数字的总排列个数 35. k = t;//k是受影响的最后数字的总排列阶乘 36. for (i = 1; i <= ii; i++){ 37. g[i] = 1; 38. } 39. for (i = n - ii + 1; i <= n; i++){ //最后ii+1个数遍历一遍 40. k /= (ii - (i - (n - ii + 1)));//相当于n！除以n 41. s = 0; 42. for (j = 1; j <= ii; j++){ 43. if (g[j]){ 44. s++; 45. if (s * k >= m){ 46. m -= (s - 1) * k; 47. g[j] = 0; 48. f[i - (n - ii)] = j + (n - ii); 49. break; 50. } 51. } 52. } 53. }//实现第m个全排列 54. //全排列产生方法不会的看这里https://blog.csdn.net/qq_41464123/article/details/80584899 55. n1 = n - ii; //n1代表全排列中前面不变的数的个数 56. dfs(0); //0到n1是不会变的 所以直接暴力模拟 57. for (i = 1; i <= ii; i++)//显然，ii是第m个排列影响到的最后几位的位数， 58. //会根据m的排列而变化 所以要判断下标和数值 59. if (pd(f[i]) && pd(n - ii + i))ans++; 60. printf("%lld\n", ans);//最后输出两部分的和 61. }
