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