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

寄与について

f:id:peroon:20200708115556p:plain

組み合わせ nCr について

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

f:id:peroon:20200708115918p:plain

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);
}