「SCOI 2003」严格n元树

题目大意：定义严格 $n$ 元树为所有非叶节点都恰好有 $n$ 个儿子，求深度为 $d$ 的严格 $n$ 元树的个数。$0 < n \leq 32, 0 \leq d \leq 16$

设 $f[i]$ 表示深度小于等于 $i$ 的严格 $n$ 元树的个数，有

$$f[i]=f[i-1]^n+1$$

另外这题的数据范围根本不可做，因为数字长度 $l$ 可以达到 $n^d$，实际上测试数据的范围是 $n^d \leq 1024$。

#include <cstdio>
#include <cstring>

const int BAS = 10000, WID = 4;

struct Big {
    int x[100000];
    Big() { memset(x, 0, sizeof x); }
    Big operator + (const int &a) {
        Big b; b.x[0] = x[0], b.x[1] = a;
        for (int i = 1; i <= b.x[0]; ++i)
            b.x[i] += x[i], b.x[i+1] = b.x[i] / BAS, b.x[i] %= BAS;
        if (b.x[b.x[0]+1]) ++b.x[0];
        return b;
    }
    void operator -= (const Big &a) {
        for (int i = 1; i <= x[0]; ++i) {
            if (x[i] < a.x[i]) --x[i+1], x[i] += BAS;
            x[i] -= a.x[i];
        }
        while (!x[x[0]] && x[0] > 1) --x[0];
    }
    void operator *= (const Big &a) {
        Big b;
        for (int i = 1; i <= x[0]; ++i)
            for (int j = 1; j <= a.x[0]; ++j)
                b.x[i+j-1] += x[i] * a.x[j], b.x[i+j] += b.x[i+j-1] / BAS, b.x[i+j-1] %= BAS;
        x[0] += a.x[0], x[1] = 0;
        for (int i = 1; i <= x[0]; ++i)
            x[i] += b.x[i], x[i+1] = x[i] / BAS, x[i] %= BAS;
        while (!x[x[0]] && x[0] > 1) --x[0];
    }
    void print() {
        printf("%d", x[x[0]]);
        for (int i = x[0] - 1; i; --i) printf("%0*d", WID, x[i]);
        puts("");
    }
} f[20];

Big fast_pow(Big a, int b) {
    Big res;
    res.x[++res.x[0]] = 1;
    for (; b; b >>= 1, a *= a)
        if (b & 1) res *= a;
    return res;
}

int main() {
    int n, d; scanf("%d%d", &n, &d); ++d;
    f[0].x[0] = 1; 
    for (int i = 1; i <= d; ++i)
        f[i] = fast_pow(f[i-1], n) + 1;
    f[d] -= f[d-1], f[d].print();
    return 0;
}

时间复杂度 $O(l^2 d \log n)$