PKU 3199 Uncle Jack

http://poj.org/problem?id=3199
n人の甥に、d枚のCDを分配したい。
このときの分配の仕方が何通りあるかという問題。
ただし、1枚も配られない人がいてもいいものとする。

多倍長で累乗。

string ret;
string add(const string&a,const string&b){
  ret.clear();

  int as=a.size(),bs=b.size();
  int c=0;
  rep(i,max(as,bs)){
    int t=c;
    if(i<as)t+=a[as-i-1]-'0';
    if(i<bs)t+=b[bs-i-1]-'0';
    c=t/10;
    t%=10;
    ret+=t+'0';
  }
  if(c)ret+=c+'0';
  reverse(ALL(ret));
  return ret;
}

string mulcret;
string multc(char m,const string&a){
  m-='0';
  mulcret.clear();

  int c=0;
  int as=a.size();
  rep(i,as){
    int t=c+m*(a[as-i-1]-'0');
    c=t/10;
    t%=10;
    mulcret+=t+'0';
  }
  if(c)mulcret+=c+'0';
  reverse(ALL(mulcret));
  return mulcret;
}

string mulret;
string mult(const string&a,string b){
  mulret.clear();
  int as=a.size();
  
  rep(i,as){
    mulret=add(mulret,multc(a[as-i-1],b));
    b+='0';
  }
  return mulret;
}

main(){
  int d;
  string n;
  while(cin>>n>>d){
    if(n=="0" && d==0)break;
    string ans="1";
    rep(i,d)ans=mult(ans,n);
    cout<<ans<<endl;
  }
}