概要

AtCoder ABC156 問題D Bouquetやってみた。modの逆元とかmodの順列組み合わせ計算の整理。

経緯

暫く仕事で忙殺されていて、コンテストにすら参画できなくて残念な状態だったのだが、一段落したのでコンテスト参加再開。これからは参加するだけでなく多少精進して色を上げていきたい。

私の実力ではABCのD問題の正解率上げていく戦略が良さげなのでとりあえず過去問含めといていくことを考えている。そんな中、AtCoder ABC156 問題D Bouquetやってみた。

結果

問題よんだら計算自体「あー大きな数の順列組み合わせのmod計算しないとダメなのね」という事はすぐ理解したのが、「でどうやってやるんだっけ？」となってしまった。むかしやってた数値計算だとmodとか整数の計算とか出てこない。

自分で一所懸命考えるのはもう少しレベルが上がってからすることにして、優秀そうな人の解法を参照してみる。参考にした提出はこちらAtCoder提出#10273434。
転記

10273434.py

     1  import sys
     2  
     3  stdin = sys.stdin
     4  
     5  ns = lambda: stdin.readline().rstrip()
     6  ni = lambda: int(stdin.readline().rstrip())
     7  nm = lambda: map(int, stdin.readline().split())
     8  nl = lambda: list(map(int, stdin.readline().split()))
     9  
    10  n,a,b = nm()
    11  mod = 10**9 + 7
    12  s = pow(2,n,mod) - 1
    13  
    14  def fur(n,r):
    15      p,q = 1,1
    16      for i in range(r):
    17          p = p*(n-i)%mod
    18          q = q*(i+1)%mod
    19      return p * pow(q,mod-2,mod) % mod
    20  
    21  print((s - fur(n,a) - fur(n,b)) % mod)
    22

2020/03時点で黄色にせまろうとしている青色の方。提出時間21:09:30か。。。速いなぁ。
コードもシンプル。。

pow(a,b,c)という便利な関数があると知る。Python pow
これみていると逆元まで計算できる。
AtCoder提出#10273434の提出者のかたは
a,pが互いに素のとき a ^ (p-2) = a ^ -1 (mod p)
の原理を使用されている様子（参考：フェルマーの小定理）。
リンクにもあるように
バージョン 3.8 で変更: For int operands, the three-argument form of pow now allows the second argument to be negative, permitting computation of modular inverses.
3引数のpowの第二引数に負の数字が許されるようになったのはPython 3.8以降。AtCoderのPythonは2020/03/12現在3.4なのでこっちの方法をつかっているのたど思われる。

14行目から関数で
p = n * (n-1) * ... * (n-r+1) (mod)
q = 1 * 2 * ... * r (mod)
return p / q (mod)
として C(n,r) = n! / (r! * (n-r)!)を計算している。

あとは
n本種類の花から任意の本数選ぶ組み合わせ 2^n
n本種類の花からa本数選ぶ組み合わせ C(n,a)
n本種類の花からa本数選ぶ組み合わせ C(n,b)
n本種類の花から一本も選ばない組み合わせ 1
で
2^n - C(n,a) - C(n,a) -1
で終了か。。答え見ちゃうとかんたんだが、さっと自分で書けるようにならないと意味ない。
furは何かの略かはわからなかった。

C++ではどうしてるのかなともう一つ提出をみてみた
AtCoder提出#10266780。
提出者のかたは2020/03/14時点で黄色の方。提出時間21:03:23。Dを最初に提出している様子ですがそれにしても速いなぁ。
転記

10266780.cpp

     1  #include <bits/stdc++.h>
     2  using namespace std;
     3  typedef long long ll;
     4  #define all(x) (x).begin(),(x).end()
     5  const ll mod=1000000007,MAX=200005,INF=1<<30;
     6  
     7  ll inv[MAX],fac[MAX],finv[MAX];
     8  
     9  ll rui(ll a,ll b){
    10      ll ans=1;
    11      while(b>0){
    12          if(b&1) ans=ans*a%mod;
    13          a=a*a%mod;
    14          b/=2;
    15      }
    16      return ans;
    17  }
    18  
    19  
    20  
    21  ll comb(ll a,ll b){
    22      ll ans=1;
    23      for(ll i=a;i>a-b;i--){
    24          ans=ans*i%mod;
    25      }
    26      for(ll i=1;i<=b;i++){
    27          ans=(ans*rui(i,mod-2))%mod;
    28      }
    29      return ans;
    30  }
    31  
    32  int main(){
    33      
    34      std::ifstream in("text.txt");
    35      std::cin.rdbuf(in.rdbuf());
    36      cin.tie(0);
    37      ios::sync_with_stdio(false);
    38      
    39      //make();
    40      
    41      int N,A,B;cin>>N>>A>>B;
    42      
    43      cout<<(mod+mod+rui(2,N)-comb(N,A)-comb(N,B)-1)%mod<<endl;
    44      
    45  }
    46

run(a,b) : a ^ b (mod)を計算する関数
comb(a,b) : C(a,b) (mod)を計算する関数
を自分で定義されていて、処理の全体は提出#10273434と同じに見える。
自作しているところをみるとPythonのPOWみたいな関数はC++ではシステム側に用意されてないのかな。

今回は結局自分ではコード書いてない。

AtCoder ABC156 問題D Bouquet modの計算と順列等

概要

経緯

結果