题目描述
100 可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。
类似这样的带分数,100 有 11 种表示法。
样例
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=10;
bool st[N],backup[N];
int ans,n;
bool check(int a,int c)
{
long long b=n*(long long)c-a*c;
if(!a||!b||!c)return false;
memcpy(backup,st,sizeof st);
while(b)
{
int x=b%10;
b/=10;
if(!x||backup[x])return false;//如果x为0或当前这一位被用过则返回false
backup[x]=true;
}
for(int i=1;i<=9;i++)if(!backup[i])return false;
return true;
}
void dfs_c(int u,int a,int c)//第几个数;当前a的值是多少;c的值是多少
{
if(u>9)return;
if(check(a,c))ans++;
for(int i=1;i<=9;i++)
if(!st[i])
{
st[i]=true;//标记状态
dfs_c(u+1,a,c*10+i);//同a
st[i]=false;
}
}
void dfs_a(int u,int a)
{
if(a>=n)return;
if(a) dfs_c(u, a, 0);//如果a不为0则枚举c最后一个0意为c的值;
for(int i=1;i<=9;i++)
if(!st[i])
{
st[i]=1;//更改状态
dfs_a(u+1,a*10+i);//传递到下一次递归更新a的值每次位数向前进一位
st[i]=0;//恢复原状
}
}
int main()
{
cin>>n;
dfs_a(0,0);//第一个0意为当前用了多少个数,第二个0意为当前a为几
cout<<ans<<endl;
return 0;
}