方法一：暴力解法

(1)先对1～9数字进行全排列
(2)对每一排列方案，划分整数部分、分子部分、分母部分三部分的位数
(3)判断每一种排列的每一种划分方案是否满足带分数方案

时间复杂度分析

$O(n\times n!)(枚举全排列)\times C(8,2)(枚举位数)=9*9！*C^2_8$

代码

#include <bits/stdc++.h>
using namespace std;

int n;
bool st[10];
vector<int> res;
int cnt;

void dfs(int m)
{
    if(m>9)
    {
        //数字枚举完之后 进行三部分位数枚举
        for(int i = 1;i <= 7;i++)
            for(int j = 1;j <= 9-i-1;j++)
            {
                int k = 0,a = 0,b = 0,c = 0;
                int p = i,q = j;
                while(p--)
                    a=a*10+res[k++];
                while(q--)
                    b=b*10+res[k++];
                while(k<9)
                    c=c*10+res[k++];
                if(a*c+b==n*c) cnt++;
            }
        return;
    }
    for(int i = 1;i <= 9;i++)
    {
        if(!st[i])
        {
            st[i] = !st[i];
            res.push_back(i);
            dfs(m+1);
            st[i] = !st[i];
            res.pop_back();
        }
    }
}

int main()
{
    cin>>n;
    dfs(1);
    cout<<cnt<<endl;
    return 0;
}

方法二：嵌套DFS

(1)枚举a
(2)枚举c
(3)对于每组a、c，判断出计算得到的b是否成立

注意

(1)算出b比枚举b的考虑情况更少，如a、c选择完还剩3位时，枚举b要考虑3!=6种情况，而由a、c计算b只用考虑一种情况
(2)理解嵌套DFS的使用，对于a、c均是排列型枚举，且先枚举a，对每一个a去枚举所有可能的c，对每一组枚举好的a、c，判断计算出来的b是否满足要求
(3)为避免破坏递归过程中的状态数组，在判断b的合理性时要使用备份数组
(4)由于$(n-a)*c$的计算结果可能超出int范围，故b必须声明为long long int

代码

#include <bits/stdc++.h>
using namespace std;

int n;
//整数 分子 分母
long long int a,b,c;
//可带分数表示的方案数
int cnt;
//1～9数字的状态数组和备份数组
bool st[10],backup[10];

//检查对于每一组枚举的a、c 算出来的b是否满足条件
bool check()
{
    //注意b要声明为long long int，防止计算出来的结果爆int范围
    b = (n-a)*c;
    //a、b、c均非零
    if(!a||!b||!c) return false;
    //用备份数组来判断 1～9是否每个数均使用仅一次
    memcpy(backup,st,sizeof(st));
    //取b的每一位进行判断
    while(b)
    {
        int x = b%10;
        b /= 10;
        //如果b含0或x重复出现
        if(!x||backup[x]) return false;
        backup[x] = 1;
    }
    //判断 1～9是否每个数均使用
    for(int i = 1;i < 10;i++ )
        if(!backup[i]) return false;
    return true;
}

void dfs_c(int used)
{
    //如果9个数均已使用则返回
    if(used > 9) return;
    //检查一下该组a、c及计算得到的b是否满足要求
    if(check()) cnt++;
    //排列型枚举c
    for(int i = 1;i < 10;i++)
    {
        if(!st[i])
        {
            st[i] = 1;
            c = c*10+i;
            dfs_c(used+1);
            c /= 10;
            st[i] = 0;
        }
    }
}

void dfs_a(int used)
{
    if(a >= n) return;
    //对于每一个有效的a 枚举一下c的取值
    if(a) dfs_c(used);
    //排列型枚举a
    for(int i = 1;i < 10;i++)
    {
        if(!st[i])
        {
            st[i] = 1;
            a = a*10+i;
            dfs_a(used+1);
            a /= 10;
            st[i] = 0;
        }
    }
}

int main()
{
    cin>>n;
    dfs_a(0);
    cout<<cnt<<endl;
    return 0;
}