题目描述
100可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9分别出现且只出现一次(不包含 0
)。
类似这样的带分数,100有 11种表示法。
样例
输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 20;
int n;
bool st[N],backup[N];
int ans;
bool check(int a,int c)//检验函数
{
int b = n * c - a * c;
if(!a||!b||!c) return false;//若a,b,c有一个为0,则不符合
memcpy(backup,st,sizeof st);
while (b)
{
int x=b%10;//x表示b的个位开始的每一位数字
b/=10;//删除最后一位
if(!x||backup[x]) return false;//不能出现0
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的dfs差不多
{
if(u==n) 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);
st[i]=false;
}
}
}
void dfs_a(int u,int a)
{
if(a>=n) return;//优化1:如果a超出n,提前退出
if(a) dfs_c(u,a,0);//a不为0,进入子节点c的排列
for(int i=1;i<=9;i++)
if(!st[i])//如果当前数位未被使用
{
st[i]=true;//标记
dfs_a(u+1,a*10+i);//进入下一位,a更新为原来的a*10+i
st[i]=false;//回溯
}
}
int main()
{
cin>>n;
dfs_a(0,0);//(已经列举了几个数字,a)
cout<<ans<<endl;// ans表示答案个数
return 0;
}