题目链接：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;
}