【问题描述】
众所周知,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.

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