#include <time.h>
#include <stdio.h>

#define N        10
#define MAX      39
#define MAX_LEN  MAX+2

int sa[N][MAX_LEN] = {
	{1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4},
	{1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}};

void Add(int a[], int b[], int c[])
{
    int i, ans = 0;

    for (i = 1; i <= a[0] && i <= b[0]; i += 1)
    {
        ans += a[i] + b[i];
        c[i] = ans % 10;
        ans /= 10;
    }
    while (i <= a[0])
    {
        ans += a[i];
        c[i++] = ans % 10;
        ans /= 10;
    }
    while (i <= b[0])
    {
        ans += b[i];
        c[i++] = ans % 10;
        ans /= 10;
    }
    if (ans)
    {
        c[i++] = ans;
    }
    c[0] = --i;
}

void Mul(int a[], int n, int b[])
{
    int i, ans = 0;

    for (i = 1; i <= a[0]; i += 1)
    {
        ans += a[i] * n;
        b[i] = ans % 10;
        ans /= 10;
    }
    while (ans)
    {
        b[i++] = ans % 10;
        ans /= 10;
    }
    b[0] = --i;
}

int judge(int a[], int b[])
{
    int i;

    for (i = 0; i < N; i += 1)
    {
        if (a[i] != b[i]) return 0;
    }
    return 1;
}

void print(int a[])
{
    int i;

    for (i = a[0]; i > 0; i -= 1)
    {
        printf("%d", a[i]);
    }
    printf("\n");
}

void cal(int a[])
{
    int i, flag[N] = {0};
    int b[MAX_LEN] = {1, 0};
    int sum[MAX_LEN] = {1, 0};

    for (i = 1; i < N; i += 1)
    {
        if (a[i])
        {
            Mul(sa[i], a[i], b);
            Add(sum, b, sum);
        }
    }
    for (i = 1; i <= sum[0]; i += 1)
    {
        flag[sum[i]] += 1;
    }

    if (judge(flag, a)) print(sum);
}

void func(int a[], int ip, int n)
{
    int i;

    if (N - 1 == ip)
    {
        a[ip] = n;
        cal(a);
        return;
    }

    for (i = n; i >= 0; i -= 1)
    {
        a[ip] = i;
        func(a, ip + 1, n - i);
    }
}

int main(int argc, char *argv[])
{
    int i, j, a[N];
    clock_t beg = clock();

    for (i = 2; i <= MAX; i += 1)
    {
        printf("[%02d]:\n", i);

        // n ^ i 的初始化
        for (j = 2; j < N; j += 1)
            Mul(sa[j], j, sa[j]);

        // 将 i 拆分为 10 个数的和
        func(a, 0, i);

        printf("\n");
    }

    printf("\nall runs %lf seconds\n", (double) (clock() - beg) / CLOCKS_PER_SEC);
    return 0;
}