みなさんプログラミングしていますか？ 私はスキルをつけようと競技プログラミングなるものに挑戦しています。競技プログラミングとは、まず数学的な問題を与えられます。そしてその問題を解くアルゴリズムを考え出し、そのアルゴリズムをコードに書いて提出する競技ですね。
私はまだまだ駆け出しのひよっこなんですが、先日modulo演算子で詰まったので、備忘録として
- moduloの性質
- moduloの使い方
- 詰まった問題の解法
Modulo、またはmod、なんて言ってますけど、%演算子といってしまう方がプログラマには分かりやすいですかね。この演算子は”左辺を右辺で割ったときの余り”を出力します。
たとえば、
10 / 3 = 3 10 % 3 = 1のような感じです、10を3で割ると1余りますからね。
競技プログラミングにおけるModulo
さて、このModuloがどのように競技プログラミングで使われるかですが、大体こんな風に出てきます。"各クエリに対して，\(その値 \bmod 10^9 + 7\) を 1 行で出力して下さい。"
つまり、"計算した本来の値 % 10e9 + 7" を出力してくださいというわけです。さて、ここで一つ目の疑問が出てくると思います。なぜそんな巨大な数で割ってその余りを出力しなければいけないか？ そしてその答えは、出題者が解として設定出来る数字を多くするためです。
つまりint型やlong型ではオーバーフローする数値を回答として使えるようにするためにModuloを使うわけです。そうすれば出力される値は必ず10e9 + 6以下となってintやlong型で扱える範囲となります。
二つ目の疑問はなぜ、10e9 + 7 という数値か？だとおもいます。それは10e9 + 7が素数だから、です。なぜ素数である必要があるかは後述するModuloの性質で説明しますが、素数ではない場合に不都合が生じるということを覚えておいてください。
二つ目の疑問はなぜ、10e9 + 7 という数値か？だとおもいます。それは10e9 + 7が素数だから、です。なぜ素数である必要があるかは後述するModuloの性質で説明しますが、素数ではない場合に不都合が生じるということを覚えておいてください。
Moduloの性質
では、Moduloの性質についてみていきましょう。まずModuloを普通の演算子であらわしてみます。
\(a \bmod b = a - b ({a \over b})\)
ん？と思われた方、C++における割り算は小数点切捨てであることをお忘れなく。このようにModuloは普通の演算子でもあらわせます。あまり使うことはないですが一応書いておきます。
続いて分配則についてお話します。
\((a + b) \bmod p = ((a \bmod p) + (b \bmod p)) \bmod p\)
足し算の場合はこれでOKです、引き算の場合はちょっと特殊で\(b\) に \(-x + p\)を代入すれば結果がマイナスにならずOKです。
掛け算についても同じように
\((ab) \bmod p = ((a \bmod p)(b \bmod p)) \bmod p\)
となります。割り算についても\(b\)に\(x^{-1}\)を代入すれば可能です。
ちなみに
\((a \bmod p) \bmod p = a \bmod p\)
という等式もあるので
\((a + b + c) \bmod p = ((a \bmod p) + (b \bmod p) + (c \bmod p)) \bmod p\)
なんてこともできます。（掛け算も可）
最後に逆数を求める方法について紹介しておきます。どうやるかというとフェルマーの小定理を使う方法を紹介させてもらいます。証明は省略させていただきますが具体的には
\(n^{-1} \bmod p = n^{p-2} \bmod p\)
の等式をつかいます。この等式には制限があって、割る数pは素数でなければいけません。上記で素数でない場合には不具合が生じると書きましたが、これのことです。
これ以外にも拡張ユークリッド互除法なんていうのもあります。難しそうだったので私は見ませんでしたが……
という等式もあるので
\((a + b + c) \bmod p = ((a \bmod p) + (b \bmod p) + (c \bmod p)) \bmod p\)
なんてこともできます。（掛け算も可）
最後に逆数を求める方法について紹介しておきます。どうやるかというとフェルマーの小定理を使う方法を紹介させてもらいます。証明は省略させていただきますが具体的には
\(n^{-1} \bmod p = n^{p-2} \bmod p\)
の等式をつかいます。この等式には制限があって、割る数pは素数でなければいけません。上記で素数でない場合には不具合が生じると書きましたが、これのことです。
これ以外にも拡張ユークリッド互除法なんていうのもあります。難しそうだったので私は見ませんでしたが……
Moduloの使い方
さて、Moduloをプログラムでどのように書くのか？ですが、基本的には階乗だったり大きな数字を掛け合わせたりするときに使います。たとえば\(n!\)とか\(n^x\)みたいな演算です。
たとえば\(n!\)はコードだとこのように書けます。
int factorial(int num){
result = 1
for(int i = 1; i <= num; i++){
result = (result * i) % 1000000007;
}
return result;
}
このコードでは1から順番に掛けていってその数字を\(\bmod 10^9+7\)しています。分配則によれば途中でいくらModuloを使おうとも結果は変わらないのでこういうことが出来るわけです。結果として変数がオーバーフローしないわけですね。詰まった問題の解法
さて、私も最初は困りまして、Moduloについての文献を読んで回ってました。詰まった問題というのがyukicoderのLayCurseさん出題の問題 No.117 組み合わせの数 です。
問題文
1 以上 N 以下の N 個の整数の中から，相異なる K 個の整数を選ぶパターンの数を C(N,K) と書きます．
1 以上 N 以下の N 個の整数の中から，相異なる K 個の整数を選び，順番に並べるパターンの数を P(N,K) と書きます．
1 以上 N 以下の N 個の整数の中から，重複を許して K 個の整数を選ぶパターンの数を H(N,K) と書きます．
（具体例はサンプル1の説明に書いてあるので必要ならば参照せよ．）
クエリが T 個与えられ，各クエリでは C(N,K),P(N,K),H(N,K) のどれかが与えられるので，その値を mod 109+7 で求めるプログラムを書いて下さい．
私の解き方
とりあえず数学における組み合わせ論についての問題、ということはすぐわかりました。つまり、
\(C(N,K) = {{N!}\over{K!(N-K)!}}\)
\(P(N,K) = {{N!}\over{(N-K)!}}\)
\(H(N,K) = {{N+K-1!}\over{K!(N-1)!}}\)
なので階乗を求める関数を作ってやればいいと思いました。
しかし、毎回階乗の演算を繰り返すと制限時間にひっかかるのであらかじめ1から10e6までの階乗の値 mod 10e9+7とその逆数を求めて配列に入れておきます。(ここらへんでちょっとカンニングしました)
あとは各クエリに対してあらかじめ計算しておいた値を使って出力してやればいいというわけです。
参考にしたサイトたち
https://en.wikipedia.org/wiki/Modulo_operation
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic
http://nagoyacoder.web.fc2.com/topcoder/topcoder_cpp4.html
http://stackoverflow.com/questions/9169167/need-help-in-mod-1000000007-questions
http://www.quora.com/Why-in-many-programming-contests-the-answer-is-required-to-be-printed-modulo-1000000007
http://yukicoder.me/problems/184
0 件のコメント:
コメントを投稿