D - 動的計画法 (abc024_d) modの世界ではこれでもかというくらい%modを入れていこう

Quiz

https://atcoder.jp/contests/abc024/tasks/abc024_d

Submit

https://atcoder.jp/contests/abc024/submissions/4028887

その他

  • 逆元の考え方は知っていた
  • サンプルでは通ったけれどテストでWAが一部出て困り、他の人のコードを見た
  • 四則演算をするごとにmodで割っていたのでそれを導入
ll ADD(ll x, ll y) { return (x+y) % mod; }
ll SUB(ll x, ll y) { return (x-y+mod) % mod; }
ll MUL(ll x, ll y) { return x*y % mod; }
  • これを導入するまでは、ほどよく計算したあとにmodを挿入していたが、上記の方法だと抜けがない
  • また、r, cを求めるときに分子・分母が負になることがあり、-123 % mod = -123 なのでmodする前にプラスになるまでmodを足したりもした
ll to_plus(ll a){
    while(a<0){
            a+=mod;
    }
    return a;
}

追記:mintという世界もある