本日の精進：逆元と組み合わせ問題 #AtCoder

おなじみの問題たち．

AtCoder Beginner Contest 034 C - 経路
最も単純な問題．nCr (mod M) を求めるだけ．
求め方については下記の記事が大変丁寧にまとめてあります．↓
「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜　(by drken氏)

この問題に関してはテーブル参照するまでもなく，分母と分子で別々に求め，最後に割れば十分．速さはO(nlogM)？早くもないけど遅くもないよ
べき乗については繰り返し自乗法を用いることで高速に求められます．参考記事(by satanic0258氏)．

ACコード↓

AC.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll M = 1000000000+7;
ll RS(ll N, ll P, ll Mod){if(P==0)return 1;else if(P%2==0){ll sq=RS(N,P/2,Mod);return sq*sq%Mod;}else{return N*RS(N,P-1,Mod)%Mod;}} //power(mod)(repeat-square,fast)


int main(void) {
  int W,H; cin >> W >> H;

  int n = W+H-2; int r = H-1;
  ll bunbo=1; ll bunshi=1;
  rep(i,r){
    bunbo = bunbo * (i+1) % M;
    bunshi = bunshi * (n-i) % M;    
  }
  cout << bunshi * RS(bunbo,M-2,M) % M << "\n";

  return 0;
}

AtCoder Beginner Contest 145 D - Knight
上記の問題の強化版．とはいえ，進み方が"上か，右か"から"(x+1,y+2)か，(x+2,y+1)か"に置き換わっただけなのでそこまで難しくはない．
数式を立てて考えれば方針はすぐに立つ．
道順が存在しないような(X,Y)の判定に少し悩んでしまった．解説ではX+Yが3の倍数であるかどうかで判定していた．自分はそこに気づく前にdouble型で処理して小数が出たらアウトという判定を思いついた．ごり押し感があってあまり好きではないが，一応AC．

ACコード↓

AC.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll M = 1000000000+7;
ll RS(ll N, ll P, ll Mod){if(P==0)return 1;else if(P%2==0){ll sq=RS(N,P/2,Mod);return sq*sq%Mod;}else{return N*RS(N,P-1,Mod)%Mod;}} //power(mod)(repeat-square,fast)

int main(void) {
  int X,Y; cin >> X >> Y;
  int a,b; double a_d, b_d;
  a_d = (double)(2*Y - X) / 3.0;
  b_d = 2*Y - a_d;
  if (floor(a_d) != a_d || a_d < 0 || b_d < 0){ //a_dが小数か，a_dが負か，b_dが負なら存在しない
    cout << 0 << "\n";
    return 0;
  }
  a = (2*Y - X) / 3;
  b = Y - 2*a;
  int n = a+b;
  ll bunbo=1; ll bunshi=1;
  rep(i,a){
    bunbo = bunbo * (i+1) % M;
    bunshi = bunshi * (n-i) %M;
  }
  cout << bunshi * RS(bunbo,M-2,M) % M << "\n";
  return 0;
}

改めて見ると全然美しくない．．．

過去の問題にこれらの更に強化版があった気がする．そちらはメモ化再帰などを使う上級問題．

AtCoder Beginner Contest 156 D - Bouquet
最近のやつ．
最初，n種類から任意個取ってくる組み合わせが2^nに等しいことに気づかずウンウン唸ってた．よく考えたら当たり前．
あとは，禁止されているa本，b本取ってくる組み合わせを求めて逆元取って全体から引いたら答え．
ただし，mod Mの世界での引き算でマイナスとなった場合，Mを足さなければならないことに注意．
また，ちゃんと掛け算する度に%Mしないとオーバーフローするので注意．=ではなく*=を使っていると嵌りやすいです．

ACコード↓

AC.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll M = 1000000000+7;
ll RS(ll N, ll P, ll Mod){if(P==0)return 1;else if(P%2==0){ll sq=RS(N,P/2,Mod);return sq*sq%Mod;}else{return N*RS(N,P-1,Mod)%Mod;}} //power(mod)(repeat-square,fast)

int main(void){
  ll n,a,b;
  cin >> n >> a >> b;
  ll ans;
  ans = RS(2,n,M); // nから任意個選ぶ組み合わせ=2^n (0本の花束はないので、後で1引く)

  ll abunbo=1,abunshi=n;
  for (int i = 1; i < a; i++){
    abunshi = abunshi * (n-i) % M; //　ここで*=を使うとオーバーフロー
    abunbo = abunbo * (i+1) % M;
  }
  ll acomb = abunshi * RS(abunbo, M-2, M) % M;
  ll bbunbo=1,bbunshi=n;
  for (int i = 1; i < b; i++){
    bbunshi = bbunshi * (n-i) % M;
    bbunbo = bbunbo * (i+1) % M;
  }
  ll bcomb = bbunshi * RS(bbunbo, M-2, M) % M;

  ans -= (acomb + bcomb + 1) % M;
  if (ans < 0) ans += M; //負の場合はM足してあげる
  cout << ans << endl;
  return 0;
}