题目
一个数是幸运数当且仅当这个数仅由 4 和 7 构成，比如 47，744，4747。
询问在 1 到 n 的全排列中字典序第 k 小的排列中，有多少个幸运数在排列中的位置编号也是幸运数。
思路
由于13!>1e9，所以只需要考虑后面13位，这个康拓逆展开就行。前面的东西数位DP一下就行。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std
;
const ll fac
[14]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800*1ll};
int f
[11],a
[11],n
,k
,x
;
int dfs(int u
,int aii
,int _0
)
{
if(u
==-1) return 1;
if(!aii
&&!_0
&&f
[u
]!=-1) return f
[u
];
int up
=aii
?a
[u
]:9,yjy
=0;
for(int i
=0; i
<=up
; i
++)
{
if(i
!=4&&i
!=7&&!(_0
&&i
==0)) continue;
yjy
+=dfs(u
-1,aii
&&i
==up
,_0
&&i
==0);
}
if(!_0
&&!aii
) f
[u
]=yjy
;
return yjy
;
}
bool check(int x
)
{
bool bz
=1;
while(x
)
{
bz
&=((x
%10==4)||(x
%10==7));
x
/=10;
}
return bz
;
}
int solve1(int x
)
{
int k
=0;
while(x
)
{
a
[k
++]=x
%10;
x
/=10;
}
return dfs(k
-1,1,1);
}
int solve2(int n
,int x
,int k
)
{
vector
<int>v
,a
;
for(int i
=n
-x
+1; i
<=n
; i
++) v
.push_back(i
);
for(int i
=x
; i
>=1; i
--)
{
int r
=k
%fac
[i
-1];
int t
=k
/fac
[i
-1];
k
=r
;
sort(v
.begin(),v
.end());
a
.push_back(v
[t
]);
v
.erase(v
.begin()+t
);
}
int j
=n
-x
+1,res
=0;
for(int i
:a
)
{
if(check(j
)&&check(i
)) res
++;
j
++;
}
return res
;
}
int main()
{
scanf("%d%d",&n
,&k
);
if(n
<=12&&1ll*k
>fac
[n
])
{
printf("-1\n"); return 0;
}
memset(f
,-1,sizeof(f
));
while(k
>fac
[x
]) x
++;
int ans
=solve1(n
-x
)-1;
ans
+=solve2(n
,x
,k
-1);
printf("%d",ans
);
}
