ぐぐりらにっき

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 <a href="http://opendata.jp.net/wordpress/wp-content/uploads/2015/08/python.png" imageanchor="1" ><img border="0" src="http://opendata.jp.net/wordpress/wp-content/uploads/2015/08/python.png" width="320" height="320" data-original-width="250" data-original-height="250" /></a> ### Type Hinting(型ヒント)とは Pythonは動的型付け言語です。 動的型付け言語とは、型があっているかどうかをプログラム実行時にチェックするような言語です。 対になる静的型付け言語はプログラム実行時ではなく、コンパイル時に型をチェックするような言語です。 静的型付け言語の例としてはC++とかJavaとかがあります。 それぞれもちろんメリットデメリットあります。 動的型付け言語であれば型を気にせず自由に書いていいので、さくさく書いていけるのですが、型が違うことによるバグを見つけるのに苦労したりします。 静的片付け言語であればそのようなバグが埋め込まれる危険性が少ない(型安全とかいう)のですが、いちいち型を指定した変数を定義しないといけないのでコードの量が多くなったりします。 そんな動的型付け言語であるPythonに、型ヒント(Type Hinting)という機能があります。 簡単に言うと、動的型付け言語であるPythonを静的片付け言語のように使うことができるのです！ といってもPythonはC++のようにコンパイルを先にするわけではないので、コンパイル時に型があっているかチェックするわけではありません…

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。 大きな数の組み合わせの10^9+7で割ったあまりを求めたくなることってありますよね(唐突) M=10^9+7とします $x={}_n C _r \ mod\ M$ の、nとかrが大きい場合。 ${}_n C _r=\frac{n!}{r!(n-r)!}$ であり、nとかrが大きい数の場合にはこれを計算したあとにMで割ったあまりを求めようとしてもオーバーフローしてしまうためにそもそも組み合わせ自体が計算できません。 でもどうにかしてxを求めたい。 そういう場面で使える方法についての話。 ### とりあえずやってみる 普通に分母がなくて、なにか大きい数の階乗のmodを計算したい場合は簡単で、 ```c int a=1; for (size_t i = 1; i <= N; i++) { a = (a * i) % M; } ``` みたいに一個ずつかけたらMで割ることを繰り返せばオーバーフローしないで済みます。 これができるのは、合同式が積については計算可能であることが背景にあります。 つまり mod Mに対して $a \equiv b$、$c \equiv d$であれば$ac \equiv bd$が成り立つことが裏にあります。 これにより、全て掛け合わせたあとにあまりを出さなくても、階乗の途中でmodを計算してもいい、ということになります。 今回難しいのは、組み合わせの式には分母にも数字が来ることです。 分母の数字も同様にmodを計算して、その数でさっき求めた分子の合同式での値を割ればいいのでは、と思われるかもしれません。 ですが、これは誤りです。合同式は割り算に対しては上手く計算できません。 ### 割り算を掛け算に変換 合同式は割り算が苦手なので、掛け算に直してしまう方法が解決策となります。 M=10^9+7は素数なので、フェルマーの小定理を用いることでこれが実現できます。 >[フェルマーの小定理] >pを素数とすると、以下の合同式がなりたつ。 > $a^{p-1}\equiv 1\ …