UVa11955 Binomial Theorem
問題文
http://uva.onlinejudge.org/external/119/11955.html
概要
二項展開せよ。
解法
反省
- 最大ケースに気をつけよ
- 場合の数は 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; }