O(n)で前計算することで、各nCrをO(1)で求められるようにする。 mod = 10**9+7 MAX = 10**5+1 #nは10**5までを想定 fact = [1]*(MAX+1) for i in range(1, MAX+1): fact[i] = (fact[i-1]*i)%mod inv = [1]*(MAX+1) for i in range(2, MAX+1): inv[i] = inv[m…

atcoder.jp1からkまでのiに対して、 ・「i回目に働くのは一番早くて何日目？」 ・「i回目に働くのは一番遅くて何日目？」 というのを格納した配列A,Bを考える。いずれも、oxの列を前から、後ろから見ていくことで可能。結論から言うと、A,Bについて、A[i] ==…

atcoder.jp必勝法ゲー。dpで遷移を見る。「j枚目で回ってきたときに勝てるか？」をdp[j]で管理する。 取れる枚数がn種類（a_1...a_n）あったとき、dp[j-a_i]が全て「win」であれば、必ず相手に「勝てる」状態で回してしまうことになるため、dp[j] = lose 逆…