AcWing 1209. 带分数——打暴力
原题链接
简单
作者:
春江花月夜ovo
,
2024-01-17 00:22:59
,
所有人可见
,
阅读 44
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using ll = long long;
bool st[10];
bool backup[10];
ll ans;
int n;
bool check(ll x)
{
if (x <= 0) return false;
memcpy(backup, st, sizeof st);
while (x)
{
int t = x % 10;
if (backup[t] || t == 0) return false;
if (!backup[t]) backup[t] = true;
x /= 10;
}
for (int i = 1; i <= 9; i ++)
if (!backup[i]) return false;
return true;
}
void dfs_2(int u, ll a, ll c)
{
if (u == 8 || a >= n) return;
for (int i = 1; i <= 9; i ++)
{
if (!st[i])
{
ll ta = (ll)a * 10 + i;
ll b = (ll)c * (n - ta);
st[i] = true;
if (check(b)) ans ++;
dfs_2(u + 1, ta, c);
st[i] = false;
}
}
}
void dfs(int u, ll c) //枚举c
{
if (u == 8) return;
for (int i = 1; i <= 9; i ++)
{
if (!st[i])
{
ll ct = c * 10 + i;
st[i] = true;
dfs_2(0, 0, ct);
dfs(u + 1, ct);
st[i] = false;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
dfs(0, 0);
cout << ans << "\n";
return 0;
}