No.1102 Remnants ～nCrの漸化式 (2種類)～

• Quiz
  • https://yukicoder.me/problems/no/1102
• AC
  • https://yukicoder.me/submissions/508089
• editorialを補足します

寄与について

組み合わせ nCr について

• Kが大きいので競プロでおなじみの方式ではなく、漸化式を使う
  • メモ化再帰する
• 漸化式にはnを減らすもの、rを減らすものがあるので適切な方を選択する。今回の場合はnを減らす漸化式を使うのが正解

nCr

map<PII,mint> mp;
mint nCr(ll n, ll r){
  auto key = MP(n,r);
  if(mp.count(key)) return mp[key];
  
  if(r==0 or r==n){
    mint mt = 1;
    return mt;
  }
  if(r==1 or r==n-1){
    mint mt = n;
    return mt;
  }
  //return mp[key] = nCr(n,r-1) * (n-r+1) / r;
  return mp[key] = nCr(n-1,r) * n / (n-r);
}