nCr メモ化再帰(DP)バージョン

• 大抵nCrを求める時はmodをとったものを返すが、以下の問題は違った
• (ABC 300点) C - Duodecim Ferra
• https://atcoder.jp/contests/abc185/tasks/abc185_c
• パスカルの三角形を上に登っていく再帰でnCrを求めればoverflowに怖がらずに済む
• AC https://atcoder.jp/contests/abc185/submissions/18780556

ll dp[300][300];

// long longを溢れない答えなら正しく返します
ll nCr(ll n, ll r){
  if(r==0 or r==n)return 1;
  if(dp[n][r]!=0)return dp[n][r];
  ll ret=nCr(n-1,r-1)+nCr(n-1,r);
  return dp[n][r]=ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll L;
    cin>>L;
    L -= 12;

    ll ans = nCr(L+11, 11);
    p(ans);
    
    return 0;
}