AcWing 1209. 带分数
原题链接
简单
作者:
geats兔
,
2024-04-07 01:51:51
,
所有人可见
,
阅读 1
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
bool st[10],backup[10];
int n,res;
bool check(int a,int c)
{
ll b=(ll)c*(n-a);
if(!a||!c||!b) return false;
memcpy(backup,st,sizeof st);
while(b)
{
int x=b%10;
b/=10;
if(!x||backup[x]) return false;
backup[x]=true;
}
for(int i=1;i<=9;i++)
if(!backup[i]) return false;
return true;
}
void dfs_c(int a,int c)
{
if(check(a,c)) res++;
for(int i=1;i<=9;i++)
{
if(st[i]) continue;
st[i]=true;
dfs_c(a,c*10+i);
st[i]=false;
}
}
void dfs_a(int a)
{
if(a>=n) return;
if(a) dfs_c(a,0);
for(int i=1;i<=9;i++)
{
if(st[i]) continue;
st[i]=true;
dfs_a(a*10+i);
st[i]=false;
}
}
int main()
{
cin>>n;
dfs_a(0);
cout<<res<<endl;
return 0;
}