自幂数：如果在一个固定的进制中，一个 n 位自然数等于自身各个数位上数字的 n 次幂之和，则称此数为自幂数。（摘自百度百科）
就如题目的例子：
8208=8^4+2^4+0^4+8^4=4096+16+0+4096
思路
显然，单纯暴力枚举每个数是否是自幂数是行不通的，时间复杂度太大。
那么我们转换思路，枚举组成自幂数用到的数呢？
设一个多重集所有元素的 $n$ 次幂的和为 $sum$。只要存在一个多重集，使得 $sum$ 的各位数字恰好对应其集合内的各个元素，就计入答案。
## 实现
自然想到直接搜索，预处理出 $0-9$ 的 $n$ 次幂的值，并且可以通过上下界可行性剪枝优化，只保留 $sum$ 在 $n$ 位以内的情况。在枚举完 $n$ 位上出现的数字组合后统计一遍答案，注意不要搜索重复情况，可按不升顺序从大数开始搜索。
附上代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int n, cnt[N];
int mi[N], ans, maxx = 1;
void check(int num) {
int now[N];
memset(now, 0, sizeof now);
while (num) {
int tmp = num%10;
num /= 10;
now[tmp] ++;
}
for (int i = 0; i < 10; i ++) {
if (now[i] != cnt[i]) return;
}
ans ++;
}
void dfs(int pos, int sum, int la) {
if (pos == n) {
check(sum);
return;
}
if (sum > maxx || mi[la]*(n-pos) + sum < maxx/10) return;
//上下界可行性剪枝
for (int i = la; i >= 0; i --) {
cnt[i] ++;
dfs(pos+1, sum+mi[i], i);
cnt[i] --;//回溯
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) maxx *= 10;
for (int i = 1; i < 10; i ++) mi[i] = i;
for (int i = 2; i <= n; i ++)
for (int j = 1; j < 10; j ++)
mi[j] *= j;
dfs(0, 0, 9);
printf("%d\n", ans);
}
```
有问题请私信，出锅了我会立即修改：）