2025年排列

排列问题描述 众所周知 Index 数是指十进制表示每位都由 4 和 7 组成的正整数 这天 Index 在研究 N 的全排列 她把它们按字典序从小到大排列 现在 Index 想知道 在第 K 个排列中 有多少 x 满足 x 是 Index 数且 A x 也是 Index 数 Input 输入格式 两个数 N 和 K

大家好,我是讯享网,很高兴认识大家。

【问题描述】

众所周知,Index数是指十进制表示每位都由4和7组成的正整数 这天,Index在研究N的全排列。她把它们按字典序从小到大排列。 现在Index想知道,在第K个排列中,有多少x满足x是Index数且A[x]也是Index数 

讯享网

Input

【输入格式】

讯享网两个数N和K。表示N个数的全排列中字典序第k小的数列。两个数之间用一个空格隔开。 

Output

【输出格式】

如果第K小的N的全排列不存在,则输入出“-1”(不含引号),否则输出x的个数。

Sample Input

sample 1:

7 4

sample 2:


讯享网

4 7

Sample Output

sample 1:

1

sample 2:

1

【提示】

字典序:如3的全排列按字典序排列:(1 2 3)(1 3 2)(2 1 3)(2 3 1)(3 1 2)(3 2 1) 

【数据范围】

讯享网对于30%的数据,N,K<=10 对于100%的数据,N,K<=10^9 

分析:我们知道,一个1~n的全排列有n!个。然后我们知道k<=10^9次方,而13!=,也就是说,只有后13个数在改变,而前1–n-13个数都是1–n-13排列的。然后我们可以用康拓逆展开求解,加个判断即可。

代码:

const hehe:Array [1..1023] of longint=(4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744, 4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777,44444,44447,44474,44477,44744,44747,44774,44777,47444, 47447,47474,47477,47744,47747,47774,47777,74444,74447,74474,74477,74744,74747,74774,74777,77444,77447,77474,77477,77744, 77747,77774,77777,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,, ,,,); var n,k,i,j,t,f,num,x,y,l,ans,h:longint; a:array [1..100] of int64; b:array [1..20] of boolean; power:Array [0..10] of longint; flag,flag1:boolean; function getsum(x:longint):longint; var s:string; i:longint; begin for i:=1 to 1023 do if hehe[i]>x then break; exit(i-1); end; begin readln(n,k); i:=1; a[1]:=1; while (a[i]*(i+1)<=k) and (i<=n) do begin inc(i); a[i]:=a[i-1]*i; end; if (i=n) and (a[i]<k) then begin writeln(-1); halt; end; x:=i+1; ans:=getsum(n-x); h:=ans; y:=getsum(n); t:=n-x; fillchar(b,sizeof(b),true); for i:=1 to x do begin if i=x then f:=0 else begin f:=(k-1) div a[x-i]+1; k:=(k-1) mod a[x-i]+1; end; num:=0; for j:=1 to x do begin if b[j] then inc(num); if num=f then begin b[j]:=false; flag:=false; flag1:=false; for l:=h+1 to y do begin if t+i=hehe[l] then flag:=true; if t+j=hehe[l] then flag1:=true; end; if flag and flag1 then inc(ans); break; end; end; end; writeln(ans); end. 
小讯
上一篇 2025-01-29 08:11
下一篇 2025-02-21 12:51

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/112517.html