/*
2001/06 開き直り数
coded by Isaku WADA
 ┌─────────────────┐
 │ 3435という数は,1桁ずつに分け │
 │て,それぞれの数を自分と同じ数で │
 │べき乗して足し合わせると,元の数 │
 │である3435になる。        │
 │ 3435 = 3^3 + 4^4 + 3^3 + 5^5  │
 │ このような数を“開き直り数”と呼│
 │ぶことにする。ちょっと考えれば1 │
 │(=1^1)もこの種の数であることがわ │
 │かる。では1以上の整数で,この1と│
 │3435以外の開き直り数をすべて見つ │
 │けていただきたい。ただし,ここで │
 │は0^0は0とする。         │
 └─────────────────┘
  Visual C++, Borland C++, LSI C-86, Turbo C で動作確認
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
 ┌───────────────────────────────┐
 │重複組合せの整数化                      │
 │                                   │
 │例えば、0 1 2の3種類(n=3,n>0)の要素があるものとします。      │
 │この中から3つ要素(r=3,r>=0)を取り出す場合を考えます。      │
 │ただし、同じ要素を複数個取り出してもよいものとします。    │
 │取り出し方は10通りあって、辞書順での番号と組合せを列挙すると、│
 │  0:(0,0,0)  1:(0,0,1)  2:(0,0,2)  3:(0,1,1)  4:(0,1,2)       │
 │  5:(0,2,2)  6:(1,1,1)  7:(1,1,2)  8:(1,2,2)  9:(2,2,2)       │
 │となります。各関数の役割は以下のとおりです。         │
 │    ・unsigned long InitRepe(int n,int r)           │
 │      テーブルを初期化し、重複組合せが何通りあるかを返します │
 │    ・unsigned long RepeToNum(int*vec)            │
 │      与えられた重複組合せの辞書順での番号を返します     │
 │      (配列 vec[0..r-1] は、小さい順にソートされていること)  │
 │    ・void NumToRepe(unsigned int long,int*vec)        │
 │      辞書順での番号から、重複組合せへ展開します       │
 └───────────────────────────────┘
*/
unsigned long**RepeTbl[2]; /* 内部テーブル(2つの行列) */

unsigned long InitRepe(int n,int r)
{
    unsigned long**a=RepeTbl[0],**b=RepeTbl[1]; int i,j;

    if (a) { for (i=0;a[i];i++) free(a[i]); free(a); RepeTbl[0]=0; }
    if (b) { for (i=0;b[i];i++) free(b[i]); free(b); RepeTbl[1]=0; }
    if (r<0||n<=0) return 0;
    RepeTbl[0]=a=(unsigned long**)malloc(sizeof*a*(r+1)); a[r]=0;
    RepeTbl[1]=b=(unsigned long**)malloc(sizeof*b*(r+1)); b[r]=0;
    if (r==0) return 1;
    for (i=0;i<r;i++) a[i]=(unsigned long*)malloc(sizeof**a*n);
    for (i=0;i<r;i++) b[i]=(unsigned long*)malloc(sizeof**b*n);
    for (i=0;i<r;i++) a[i][n-1]=1;
    for (j=1;j<n;j++) a[r-1][j]=1;
    for (i=r-2;i>=0;i--) for (j=n-2;j>0;j--)
        a[i][j]=a[i][j+1]+a[i+1][j];
    for (i=0;i<r;i++) a[i][0]=0;
    for (i=0;i<r;i++) for (j=1;j<n;j++)
        b[i][j-1]=a[i][j]+=a[i][j-1];
    for (i=r-2;i>=0;i--) for (j=0;j<n-1;j++) b[i][j]+=b[i+1][j];
    if (n==1) for (i=0;i<r;i++) b[i][0]=1;
    else for (i=0;i<r;i++) b[i][n-1]=b[i][n-2]+1;
    for (i=0;i<r;i++) for (j=1;j<n;j++) if (b[i][j]<=b[i][j-1])
    { printf("InitRepe(%d,%d)で桁があふれました\n",n,r); exit(1); }
    return b[0][n-1];
}

unsigned long RepeToNum(int*vec)
{
    int i; unsigned long*p,num=0;

    for (i=0;(p=RepeTbl[0][i])!=0;i++) num+=p[vec[i]];
    return num;
}

void NumToRepe(unsigned long num,int*vec)
{
    int i,j=0; unsigned long*p;

    for (i=0;(p=RepeTbl[1][i])!=0;i++) {
        while (p[j]<=num) j++;
        num-=RepeTbl[0][i][j]; vec[i]=j;
    }
}

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(void)
{
    double StartTime=clock();
    int i,vec[10],num[10],su[10],j;
    unsigned long ans,k,wk,tm,rui[10],cz[10],bnd=InitRepe(10,10);

    for (i=0;i<=9;i++)
    { rui[i]=i; for (j=1;j<i;j++) rui[i]*=i; }
    cz[0]=1;
    for (i=1;i<=9;i++) cz[i]=cz[i-1]*10;
    for (k=1;k<bnd;k++) {
        NumToRepe(k,vec);
        for (i=0;i<=9;i++) num[i]=0;
        for (i=0;i<=9;i++) num[vec[i]]++;
        for (ans=i=0;i<=9;i++) ans+=rui[i]*num[i];
        for (i=0;i<=9;i++) su[i]=0;
        for (wk=ans,i=9;i>=0;i--) {
            for (tm=cz[i],j=0;wk>=tm;j++,wk-=tm) ;
            if (su[j]++>=num[j]) { ans=0; break; }
        }
        if (ans) for (i=1;i<=9;i++)
         if (su[i]!=num[i]) { ans=0; break; }
        if (ans) printf("%lu\n",ans);
    }
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}