AcWing 1209. 带分数
原题链接
简单
作者:
风起于浮萍之末
,
2024-02-12 11:03:35
,
所有人可见
,
阅读 28
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
bool st[N], backup[N];
int ans;
bool check(int a, int c)
{
long long b = n * (long long)c - a * c;//获取b
if (!a || !b || !c) return false;// 不能为空
memcpy(backup, st, sizeof st);//多次操作,我们对备份进行操作,不影响原数组
while (b)//就是取出b的每一位 判断是否满足条件
{
int x = b % 10; // 取个位
b /= 10; // 个位删掉
if (!x || backup[x]) return false;// 不能为0 之前没有出现过
backup[x] = true;//用过了
}
for (int i = 1; i <= 9; i ++ )//每一位元素都使用了
if (!backup[i])
return false;
return true;
}
void dfs_c(int u, int a, int c)
{
if (u > 9) return;//当前枚举到哪个位置了 0-8位置
if (check(a, c)) ans ++ ;//检测a和c是否满足条件
for (int i = 1; i <= 9; i ++ )
if (!st[i])
{
st[i] = true;
dfs_c(u + 1, a, c * 10 + i);//枚举u的下一个位置 更新c
st[i] = false;
}
}
void dfs_a(int u, int a)// u表示当前已经用了多少个
{
if (a >= n) return;// a的范围
if (a) dfs_c(u, a, 0);// 对于每一种a方案 进行c的测试
for (int i = 1; i <= 9; i ++ )
if (!st[i])//没用过
{
st[i] = true;//打标机
dfs_a(u + 1, a * 10 + i);//枚举下一个位置 同时更新a
st[i] = false;
}
}
int main()
{
cin >> n;
dfs_a(0, 0);
cout << ans << endl;
return 0;
}