E2-D

题目要求

对任意正整数，如果其各位数的n次方之和等于它本身，那么它被称为一个n元数。给定n，求出所有n元数的和。

核心算法和原理

• Brute-Force想想都知道不行。

• 注意到对任何一个整数序列，如果其能够排列成为一个n元数，那么这个n元数一定唯一。

• 本质上是一个元素可重复的组合问题。dfs参数解释：c为此时序列的最后一个元素，res为序列对应的n次方之和，minRes为目前的序列所排列成为的无前导0的最小数（不完全准确），digit为10^bit（序列长度）。

• 递归树：最大元素出现在序列前部，并且元素可重复（即每一个元素的子树一定以小于等于它的结点及其子树构成）。

• 剪枝条件设计为 minRes是否大于res，若是的话说明再怎么加都不可能组成这么小的n元数，剪掉其子树。

• 细节：在处理minRes的前导0的时候，用一个估计值digit / 10来近似处理了。

代码

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

int n, t;
long long ansAll;
long long pows[13];   //pows[i] denote i^n
int cnt[10];  //0-9 cnt(composition)
int test[10]; //0-9 cnt(number)

long long fpm(long long a, long long b);
void generatePow(int n);
int check(long long pow);
void dfs(int c, long long res = 0, long long minRes = 0, long long digit = 1);

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> t;
    while(t--){
        cin >> n;
        generatePow(n);
        dfs(9);
        cout << ansAll << endl;
        ansAll = 0;
        memset(cnt, 0, sizeof(int));
    }
    return 0;
}

long long fpm(long long a, long long b) {
    long long ans = 1;
    for ( ; b; b >>= 1, a = a * a)
        if (b & 1) ans = ans * a;
    return ans;
}

void generatePow(int n){    //generate an n times sequence of 0-9
    for(int i = 1; i < 10; i++) {
        pows[i] = fpm(i, n);
    }
}

int check(long long pow){
    for(int i = 0; i < 10; i++){
        test[i] = 0;
    }

    while(pow > 0){
        int i = pow % 10;
        test[i]++;
        //check each digit of pow, if some number appears more than its composition's: false
        if(test[i] > cnt[i]){
            return 0;
        }
        pow /= 10;
    }

    for(int i = 0; i < 10; i++) {
        if (test[i] != cnt[i]) {
            return 0;
        }
    }
    return 1;
}

void dfs(int c, long long res , long long minRes, long long digit){
    if(minRes > res){
        return;
    }

    ansAll += check(res) * res;
    for(int i = 0; i <= c; i++){
        cnt[i]++;
        dfs(i, res + pows[i], minRes + max(digit / 10, digit * i), digit * 10);
        cnt[i]--;
    }
}