UVa11955 Binomial Theorem

問題文
http://uva.onlinejudge.org/external/119/11955.html

概要
二項展開せよ。

解法

  • パスカルの三角形のDP(orメモ化再帰
    • long long
  • 係数、乗数、文字の場合分け

反省

  • 最大ケースに気をつけよ
  • 場合の数は long long にならないか?今回は関係ないが、確率の場合は「分母は long double」を疑うとよい。
#include <bits/stdc++.h>
 
using namespace std;
 
int toInt(string s) { return atoi(s.c_str()); }
 
long long dp[55][55];
 
int main() {
   
  dp[0][0] = 1;
  for(int i=0; i<55; i++) {
    for(int j=0; j<55; j++) {
      dp[i+1][j] += dp[i][j];
      dp[i+1][j+1] += dp[i][j];
    }
  }
   
  int Tc; cin >> Tc;
  for(int Tcnt=1; Tcnt<=Tc; Tcnt++) {
    string s; cin >> s;
    int N = s.size();
    int pos = s.find('+');
    int posh = s.find('^');
    string lhs = s.substr(1, pos-1);
    string rhs = s.substr(pos+1, posh-pos-2);
     
    int K = toInt(s.substr(posh+1));
     
    cout << "Case " << Tcnt << ": ";
     
    for(int i=0; ; i++) {
      if(dp[K][i] == 0) break;
      if(i) cout << "+";
      if(dp[K][i] == 1) {}
      else { cout << dp[K][i] << "*"; }
      if(K-i>=1) cout << lhs;
      if(K-i> 1) cout << "^" << K-i;
      if(K-i>=1 && i>=1) cout << "*";
      if(i>=1) cout << rhs;
      if(i> 1) cout << "^" << i;
    }
    cout << endl;
  }
  return 0;
}