AcWing
1209. 带分数
可以先枚举1~9所有的排列情况，对每种排列情况，划分为三个数a，b，c，验证是否满足n = a + b/c. 其中，a的枚举，其位数只需从1枚举到6，c的枚举需要至少给b留出一个数。相当于从8个间隙中插2块板。总的时间复杂度为$9!\times 9\times C_8^2 \approx 9\times 10^7$.
暴力美学_(:з」∠)_
#include <bits/stdc++.h>
using namespace std;
int n;
int a[12], res = 0;
bool visited[12];
typedef long long LL;
int abc(){
int cnt = 0;
for(int i = 1; i <= 6; i++){
int aa = 0;
for(int j = 1; j <= i; j++) aa = aa * 10 + a[j];
for(int j = 9; j >= i + 2; j--){
int cc = 0;
for(int k = j; k <= 9; k++) cc = cc * 10 + a[k];
LL bbv = (LL)cc * n - (LL)cc * aa;
LL bb = 0;
for(int k = i + 1; k <= j - 1; k++) bb = bb * 10 + a[k];
if(bbv == bb){
// cout << aa << ' ' << bb << ' ' << cc << '\n';
cnt++;
}
}
}
return cnt;
}
void dfs(int digit){
if(digit > 9){
res += abc();
return;
}
for(int i = 1; i <= 9; i++){
if(!visited[i]){
visited[i] = true;
a[digit] = i;
dfs(digit + 1);
visited[i] = false;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
dfs(1);
cout << res << '\n';
return 0;
}