こんにちは。気分が悪くて半日お布団の中にいたとーです。
ARC013A
以前解けなかったきりしばらく放置していた問題
荷物の長さの順列を持ってきて、与えられた容器の辺をその順列の第一、二、三要素で割り切って、掛け合わせたものが容器に入る荷物の数なので、それの最大値を求めるだけ
ABC110D
これも以前解けなかった問題
素因数分解して、指数の部分を分割すればよいっていう賢いやり方が書いてあった すごい
さて実装の段で、nCkをかけていって、最後に10**9+7で割る操作が入ったのだが、
import math n = int(input()) k = int(input()) a = (math.factorial(n))%(10**9+7) b = (math.factorial(k)%(10**9+7)) c = (math.factorial(n-k)%(10**9+7)) print((a*pow(b*c,10**9+5,10**9+7))%(10**9+7))
この逆元を使うやり方だとTLEし、
n,k = map(int,input().split()) cur = 1 for i in range(k+1,n+1): cur *= i for j in range(1,n-k+1): cur = cur//j print(cur%(10**9+7))
こっちの普通に掛け算をする方では通った なんで
多分n,kがそんなに大きくないときは、後者の計算量もそれほどではないのでこっちの方が速い（nCk自体の計算はkに依存するので）のではないかとか思ったけど、n=10**5,k = 100とかでも前者の方が速かった（し、後者に至っては間に合わない）ので何とも言えない
まあこういうケースもあるということを覚えておく
EDPC D,I
どっちもTLEだったけどPyPyにしたら通った マジ？
PyPyを使うデメリットは分かってないけど、速いんだったらこっちの方がよくないですか
