题目描述

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

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 10;
int ans, n;
bool sign[N], backup[N];

bool check(int a, int c){
    int b = (n-a)*c;
    if(b <= 0) return false;

    memcpy(backup, sign, sizeof(sign));
    while(b){
        if(backup[b%10] || !(b%10)) return false;
        backup[b%10] = true;
        b /= 10;
    }
    for(int i = 1; i < N; i++)
        if(!backup[i]) return false;
    return true;
}

void dfs_c(int t, int a, int c){
    if(t >= N) return;
    if(c && check(a, c)) ans++;

    for(int i = 1; i < N; i++)
        if(!sign[i]){
            sign[i] = true;
            dfs_c(t+1, a, c*10+i);
            sign[i] = false;
        }
}

void dfs_a(int t, int a){
    if(t >= N) return;
    if(a) dfs_c(1, a, 0);

    for(int i = 1; i < N; i++)
        if(!sign[i]){
            sign[i] = true;
            dfs_a(t+1, a*10+i);
            sign[i] = false;
        }
}

int main(){
    cin >>n;

    //第几位放什么，a的值
    dfs_a(1, 0);

    cout <<ans;
    return 0;
}