ABC156 D問「Bouquet」

問題リンク

atcoder.jp

問題文

回答プログラム

import math
n, a, b = map(int, input().split(" "))
mod_num = 10**9 + 7

# n, aは正整数(n >= a), pは素数
def comb_mod(n, a, p):
  X = 1
  for num in range(n, n-a, -1):
    X *= num
    X %= p
  Y = math.factorial(a) % p
  return (X * (pow(Y, p-2, p))) % p

print((pow(2, n, mod_num) - (comb_mod(n, a, mod_num) + comb_mod(n, b, mod_num) + 1)) % mod_num)

解説

冪剰余計算と組合せ剰余計算が必要となる問題． どちらも高速化できる手法があるので説明する．

まず冪剰余計算については，pythonの既存関数powを利用することで高速に求められる．

Example:

>>> pow(10, 3, 7)
6
>>> pow(10**9, 4000, 123456)
9088

一方，組合せ剰余計算については，少し工夫しないといけない． 以下の式変形を見てみよう．

組合せ「剰余」計算においては，上記の式変形を利用して高速計算できる(ただしpは素数)．理由としては，Y^p-2はpow関数を利用することで高速に計算できるためである．

この手の問題が出たら，いちいちアルゴリズムを考えるのは手間なので，すぐ利用できる形でドキュメントに残しておくと良いかもしれない．