- #include<cstdio>
- #include<cstring>
- #include<iostream>
- using namespace std;
- #ifndef BIGNUM
- #define BIGNUM
- class BigNum
- {
- #define MAXSIZEOFBIGNUM 500
- #define BASE 10
- #define DLEN 1
- public:
- int Len;
- int d[MAXSIZEOFBIGNUM];
- public:
- BigNum(void);
- BigNum(const int);
- BigNum(const char *);
- BigNum(const BigNum &);
- BigNum & operator = (const BigNum &);
- void clear(void);
- friend istream& operator>>(istream&,BigNum&);
- friend ostream& operator<<(ostream&,BigNum&);
- bool operator == (const BigNum &) const;
- bool operator > (const BigNum &) const;
- bool operator < (const BigNum &) const;
- bool operator >= (const BigNum &) const;
- bool operator <= (const BigNum &) const;
- BigNum operator + (const BigNum &) const;
- BigNum operator - (const BigNum &) const;
- BigNum operator * (const BigNum &) const;
- BigNum operator / (const BigNum &) const;
- BigNum operator % (const BigNum &) const;
- void operator ++ (void);
- void operator -- (void);
- BigNum operator + (const int &) const;
- BigNum operator - (const int &) const;
- BigNum operator * (const int &) const;
- BigNum operator / (const int &) const;
- int operator % (const int &) const;
- BigNum operator ^ (const int &) const;
- ~BigNum () {}
- };
- BigNum::BigNum(){
- Len=0;
- memset(d,0,sizeof(d));
- }
- BigNum::BigNum(const int ops){
- int x=ops;
- Len=0;
- memset(d,0,sizeof(d));
- while (x)
- {
- Len++;
- d[Len]=x%BASE;
- x/=BASE;
- }
- }
- BigNum::BigNum(const char * ops){
- int L=strlen(ops)-1,b=0;
- memset(d,0,sizeof(d));
- while (ops[b]=='0') b++;
- Len=0;
- while (L-b+1>=DLEN)
- {
- int x=0;
- for (int i=L-DLEN+1;i<=L;i++) x=x*10+ops[i]-'0';
- Len++;
- d[Len]=x;
- L-=DLEN;
- }
- int x=0;
- for (int i=b;i<=L;i++) x=x*10+ops[i]-'0';
- Len++;
- d[Len]=x;
- }
- BigNum::BigNum(const BigNum &ops):Len(ops.Len){
- memset(d,0,sizeof(d));
- for(int i=1;i<=Len;i++) d[i]=ops.d[i];
- }
- BigNum & BigNum::operator = (const BigNum &ops){
- memset(d,0,sizeof(d));
- Len=ops.Len;
- for(int i=1;i<=Len;i++)
- d[i]=ops.d[i];
- return *this;
- }
- void BigNum::clear(void){
- for (int i=1;i<=MAXSIZEOFBIGNUM-2;i++)
- {
- if (d[i]<0)
- {
- d[i]+=BASE;
- d[i+1]--;
- }
- if (d[i]>=BASE)
- {
- d[i]-=BASE;
- d[i+1]++;
- }
- }
- for (int i=MAXSIZEOFBIGNUM-1;i>=1;i--)
- if (d[i]>0)
- {
- Len=i;
- return;
- }
- Len=0;
- }
- istream& operator>>(istream &in,BigNum &ops){
- char str[MAXSIZEOFBIGNUM+100];
- in>>str;
- int L=strlen(str),b=0;
- while (str[b]=='0') b++;
- ops.Len=0;
- for (int i=L-1;i>=b;i--)
- {
- ops.Len++;
- ops.d[ops.Len]=str[i]-'0';
- }
- return in;
- }
- ostream& operator<<(ostream& out,BigNum& ops){
- for (int i=ops.Len;i>=1;i--) out<<ops.d[i];
- if (ops.Len==0) out<<"0";
- return out;
- }
- bool BigNum::operator == (const BigNum &ops) const{
- if (Len!=ops.Len) return false;
- for (int i=Len;i>=1;i--)
- if (d[i]!=ops.d[i]) return false;
- return true;
- }
- bool BigNum::operator > (const BigNum &ops) const{
- if (Len<ops.Len) return false;
- else if (Len>ops.Len) return true;
- else
- {
- for (int i=Len;i>=1;i--)
- if (d[i]<ops.d[i]) return false;
- else if (d[i]>ops.d[i]) return true;
- }
- return false;
- }
- bool BigNum::operator < (const BigNum &ops) const{
- if (Len<ops.Len) return true;
- else if (Len>ops.Len) return false;
- else
- {
- for (int i=Len;i>=1;i--)
- if (d[i]<ops.d[i]) return true;
- else if (d[i]>ops.d[i]) return false;
- }
- return false;
- }
- bool BigNum::operator >= (const BigNum &ops) const{
- if (Len<ops.Len) return false;
- else if (Len>ops.Len) return true;
- else
- {
- for (int i=Len;i>=1;i--)
- if (d[i]<ops.d[i]) return false;
- else if (d[i]>ops.d[i]) return true;
- }
- return true;
- }
- bool BigNum::operator <= (const BigNum &ops) const{
- if (Len<ops.Len) return true;
- else if (Len>ops.Len) return false;
- else
- {
- for (int i=Len;i>=1;i--)
- if (d[i]<ops.d[i]) return true;
- else if (d[i]>ops.d[i]) return false;
- }
- return true;
- }
- BigNum BigNum::operator + (const BigNum &ops) const{
- BigNum ret(*this);
- for (int i=1;i<=ops.Len;i++) ret.d[i]+=ops.d[i];
- ret.clear();
- return ret;
- }
- BigNum BigNum::operator - (const BigNum &ops) const{
- BigNum ret(*this);
- for (int i=ops.Len;i>=1;i--) ret.d[i]-=ops.d[i];
- ret.clear();
- return ret;
- }
- BigNum BigNum::operator * (const BigNum &ops) const{
- BigNum ret,now(*this);
- for (int i=1;i<=now.Len;i++)
- for (int j=1;j<=ops.Len;j++)
- ret.d[i+j-1]+=now.d[i]*ops.d[j];
- for (int i=1;i<=MAXSIZEOFBIGNUM-2;i++)
- if (ret.d[i]>=BASE)
- {
- ret.d[i+1]+=ret.d[i]/BASE;
- ret.d[i]%=BASE;
- }
- for (int i=MAXSIZEOFBIGNUM-1;i>=1;i--)
- if (ret.d[i]>0)
- {
- ret.Len=i;
- break;
- }
- return ret;
- }
- BigNum BigNum::operator / (const BigNum &ops) const{
- BigNum now=(*this),div,mod;
- div.Len=now.Len;
- mod.Len=0;
- for (int j=now.Len;j>=1;j--)
- {
- mod.Len++;
- for (int p=mod.Len;p>=2;p--) mod.d[p]=mod.d[p-1];
- mod.d[1]=now.d[j];
- while (mod>=ops)
- {
- div.d[j]++;
- mod=mod-ops;
- }
- if (mod.Len==1 && mod.d[1]==0) mod.Len--;
- }
- div.clear();
- mod.clear();
- return div;
- }
- BigNum BigNum::operator % (const BigNum &ops) const{
- BigNum now=(*this),div,mod;
- div.Len=now.Len;
- mod.Len=0;
- for (int j=now.Len;j>=1;j--)
- {
- mod.Len++;
- for (int p=mod.Len;p>=2;p--) mod.d[p]=mod.d[p-1];
- mod.d[1]=now.d[j];
- while (mod>=ops)
- {
- div.d[j]++;
- mod=mod-ops;
- }
- if (mod.Len==1 && mod.d[1]==0) mod.Len--;
- }
- div.clear();
- mod.clear();
- return mod;
- }
- void BigNum::operator ++ (void){
- d[1]++;
- for (int i=1;i<=MAXSIZEOFBIGNUM-2;i++)
- if (d[i]>=BASE)
- {
- d[i]-=BASE;
- d[i+1]++;
- }
- else break;
- if (d[Len+1]>0) Len++;
- }
- void BigNum::operator -- (void){
- d[1]--;
- for (int i=1;i<=MAXSIZEOFBIGNUM-2;i++)
- if (d[i]<0)
- {
- d[i]+=BASE;
- d[i+1]--;
- }
- else break;
- if (d[Len]==0) Len--;
- }
- BigNum BigNum::operator + (const int & ops) const{
- BigNum ret=(*this);
- ret.d[1]+=ops;
- ret.clear();
- return ret;
- }
- BigNum BigNum::operator - (const int & ops) const{
- BigNum ret=(*this);
- ret.d[1]-=ops;
- ret.clear();
- return ret;
- }
- BigNum BigNum::operator * (const int & ops) const{
- BigNum ret(*this);
- for (int i=1;i<=ret.Len;i++) ret.d[i]*=ops;
- for (int i=1;i<=MAXSIZEOFBIGNUM-2;i++)
- if (ret.d[i]>=BASE)
- {
- ret.d[i+1]+=ret.d[i]/BASE;
- ret.d[i]%=BASE;
- }
- for (int i=MAXSIZEOFBIGNUM-1;i>=1;i--)
- if (ret.d[i]>0)
- {
- ret.Len=i;
- return ret;
- }
- ret.Len=0;
- return ret;
- }
- BigNum BigNum::operator / (const int & ops) const{
- BigNum ret;
- int down=0;
- for(int i=Len;i>=1;i--)
- {
- ret.d[i]=(d[i]+down*BASE)/ops;
- down=d[i]+down*BASE-ret.d[i]*ops;
- }
- ret.Len=Len;
- while(ret.d[ret.Len]==0 && ret.Len>1)
- ret.Len--;
- return ret;
- }
- int BigNum::operator % (const int &ops) const{
- int mod=0;
- for(int i=Len;i>=1;i--)
- mod=((mod*BASE)%ops+d[i])%ops;
- return mod;
- }
- BigNum BigNum::operator ^ (const int &ops) const{
- BigNum t,ret(1);
- if(ops==0)return ret;
- if(ops==1)return *this;
- int m=ops,i;
- while(m>1)
- {
- t=*this;
- for(i=1;(i<<1)<=m;i<<=1)
- t=t*t;
- m-=i;
- ret=ret*t;
- if(m==1)ret=ret*(*this);
- }
- return ret;
- }
- #endif
- BigNum C(int N,int K)
- {
- BigNum ret(1);
- for (int i=0;i<K;i++) ret=ret*(N-i);
- for (int i=1;i<=K;i++) ret=ret/i;
- return ret;
- }
- BigNum f[60];
- int main()
- {
- f[1]=1;
- f[2]=1;
- f[3]=4;
- f[4]=38;
- for (int i=5;i<=50;i++)
- {
- int pow=i*(i-1)/2;
- BigNum T=(BigNum)2^pow;
- for (int j=1;j<i;j++)
- {
- BigNum tmp,com;
- tmp=(BigNum)2^((i-j)*(i-j-1)/2);
- tmp=tmp*f[j];
- com=C(i-1,j-1);
- tmp=tmp*com;
- T=T-tmp;
- }
- f[i]=T;
- }
- int N;
- while (scanf("%d",&N)!=EOF,N!=0) cout<<f[N]<<endl;
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/251120137470.html
来源: http://www.codesnippet.cn/detail/251120137470.html