AcWing 5052. 排列--带注释
原题链接
困难
作者:
梦念小袁
,
2023-07-16 13:17:05
,
所有人可见
,
阅读 193
本题考虑到排列的数量呈现阶乘的性质
当n很大的时候对于后面的数只有后13 个数可能存在全排
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=20;
bool st[N];
int n,m;
int ans;
int fact(int k){// 计算全排个数
LL res=1;
for(int i=1;i<=k;i++){
res=res*i;
if(res>m) return m+1;
}
return res;
}
int get(int x){// 得到对应的位数
int k=1,r=m;
while(fact(k)<r) k++;// 表示从后面来看是否是满足全排数量
// 最后得到的就是满足要求的k也就是满足全排数的数
if(x<=n-k) return x;// 表示前面的数是不需要变化的
memset(st,0,sizeof st);
for(int i=n-k+1;i<=n;i++)// 表示来看后面的每一个位置
for(int j=1;j<=k;j++)// 表示要填的每一个数字先用1-k来代替
if(!st[j]){// 这个数要是没有使用过的话
int t=fact(n-i);// 表示这个数固定为多少之后后面的直接全排
if(t<r) r-=t;// 表示用这个数开头的不满足
else{// 表示用这个开头的数满足要求
if(x==i) return j+n-k;// 表示枚举到了我要求的位置
st[j]=true;
break;
}
}
}
bool check(int x){// 判断是对应的位数是否是满足要求的
string s=to_string(get(x));
for(auto &v:s)
if(v!='4'&&v!='7') return false;
return true;
}
void dfs(LL u){// 1022个组合数
if(u>n) return ;
if(u&&check(u)) ans++;
dfs(u*10+4);
dfs(u*10+7);
}
int main(){
cin>>n>>m;
if(fact(n)<m) cout<<-1<<endl;// 全排依旧到不到这个要求直接输出-1
else{
dfs(0);// 找到答案
cout<<ans<<endl;
}
return 0;
}
小数据直接爆搜
#include <bits/stdc++.h>
using namespace std;
const int N=15;
int a[N];
int n,k,ans;
bool check(int x){
while(x){
if(x%10!=4&&x%10!=7) return false;
x/=10;
}
return true;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) a[i]=i;
int cnt=1;
do{
if(cnt==k){
for(int i=1;i<=n;i++){
if(check(i)&&check(a[i])){
ans++;
}
}
cout<<ans<<endl;
return 0;
}
cnt++;
}while(next_permutation(a+1,a+1+n));
cout<<-1<<endl;
return 0;
}