题目描述
100 可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。
类似这样的带分数,100 有 11 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<106
样例
输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=30;
int n;
bool st[N],backup[N];
int ans;
//dfs嵌套;
//先dfs_a,在dfs_a的每个叶子节点(即每个a的方案)下dfs_c(c的方案,在c中check(a,c);b=c*n-a*c(由等式可得))
bool check(int a,int c){
int b=c*n-a*c;
memcpy(backup,st,sizeof st);
if(!a||!b||!c)return false;
while(b){
int x=b%10;//取个位
b/=10;//各位删掉
if(!x||backup[x])return false;//若该位数字为零,或者已经出现过,则false
backup[x]=true;//标记该个位数字出现
}
for(int i=1;i<=9;i++)
if(!backup[i])return false;//检查1~9是否都各出现一次
return true;
}
void dfs_c(int u,int a,int c){//u表示已经用了多少数,a表示a方案,c表示当前c
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);//分支,c后加入i,更新c(c=c*10+i)
st[i]=false;//恢复现场
}
}
}
void dfs_a(int u,int a){//u表示1~9中已经用了多少数,a表示当前a
if(a>=n)return;//若a已大于n,则返回false
if(a)dfs_c(u,a,0);//对a的叶子节点(即a的方案)嵌套c的dfs,枚举c的方案,并检查b
for(int i=1;i<=9;i++)
{
if(!st[i]){
st[i]=true;
dfs_a(u+1,a*10+i);//分支,a后加入i,更新a(a=a*10+i)
st[i]=false;//恢复现场
}
}
}
int main(){
scanf("%d",&n);
dfs_a(0,0);//用了0个数,a此时为0
cout<<ans;
return 0;
}