题目链接：AcWing 1209. 带分数
100 可以表示为带分数的形式：100=3+69258/714
还可以表示为：100=82+3546/197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100有 11种表示法。
输入格式 一个正整数。
输出格式 输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围 1≤N<106
输入样例1： 100
输出样例1： 11
输入样例2： 105
输出样例2： 6
程序说明：
先求出1~9的全排列，然后划分成三段(隔板法)，判断每段是否满足要求。
代码如下：
#include <iostream>
using namespace std
;
int a
[10], st
[10], n
, res
;
int cal(int l
, int r
) {
int t
= 0;
for(int i
= l
; i
<= r
; i
++)
t
= t
* 10 + a
[i
];
return t
;
}
void dfs(int k
) {
if(k
== 9) {
for(int i
= 0; i
< 7; i
++) {
for(int j
= i
+ 1; j
< 8; j
++) {
int a
= cal(0, i
);
int b
= cal(i
+ 1, j
);
int c
= cal(j
+ 1, 8);
if(c
* n
== c
* a
+ b
)
res
++;
}
}
return;
}
for(int i
= 1; i
<= 9; i
++) {
if(!st
[i
]) {
st
[i
] = 1;
a
[k
] = i
;
dfs(k
+ 1);
st
[i
] = 0;
}
}
}
int main() {
cin
>>n
;
dfs(0);
cout
<<res
;
return 0;
}
