sugarknri https://blog.hatena.ne.jp/sugarknri/ メモ https://sugarknri.hatenablog.com/ 問題はこちら No.117 組み合わせの数 - yukicoder素直に階乗で計算するだけ C(N,K)はによる単純なループによりO(K)で計算できるけど、KTが大きいのでこれではTLEになる なので、事前に階乗を計算しておけば、各クエリは定数時間で答えられるP:=10^9+7は素数なので、K<PにおいてK!はPを因数に持たず、互いに素であることから、mod PにおけるK!の逆元は存在する。 逆元はフェルマーの小定理により求める横着をして、階乗の逆元を毎回求めているのでちょっと遅い //繰り返し二乗法 long p(long a,int i){return i?p(a*a%P,i/2)*(i%… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsugarknri.hatenablog.com%2Fentry%2F2016%2F12%2F06%2F053727" title="yukicoder No.117 組み合わせの数 - メモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=%5Cprod_%7Bi%3D1%7D%5EK%20%5Cfrac%7BN%2B1-i%7D%7Bi%7D Hatena Blog https://hatena.blog 2016-12-06 05:37:27 rich https://sugarknri.hatenablog.com/entry/2016/12/06/053727 1.0 100%