経緯
はじめまして。
先週から競プロに取り組み始めた初学者です。
昨日、Atcoder Grand ContestというAtcoderの中でも難易度が高いコンテストがあり、初めて出場してみました。
昨日のものは、その中でも難化していて、スピードによっては２完で橙パフォがつくほどだったそうです。
私は１問しか解けずに終わりましたが、１問目の難易度にも驚きました(ABCと違いすぎた)
２問目の解説を読んでいるとLucasの定理という定理が出てきました。
(気になる方は問題文も読んでみてください)
あたかも常識のように出てきて驚きました笑
「Lucasの定理 競プロ」でググったところ、Hitしたので覚えておくべきだと思い、説明と実装をしようと思い今に至ります。(pythonで実装しています)
ps.)競プロ界隈では常識の定理ですか？教えていただける方いましたら幸いです。
Lucasの定理って一体？
p: 素数
m,n: 非負整数
C(n,k) := (n個の中からk個を選ぶ場合の数)
とした時に
C(m,n) \equiv \prod_{i=0}^l C(m_i, n_i) \ \ \ \ (mod\ p) \\
ただし、
m_lm_{l−1}⋯m_1m_0 := (mのp進数表示)\\
n_ln_{l−1}⋯n_1n_0 := (nのp進数表示)
とする。
結局何がしたいのか
私なりにまとめてみると
「C(n,k)の余りを求める時に楽するための定理」
みたいに解釈しました。
今回の場合の例
今回のコンテストの問題では、入力の数字全てに対するC(n,k)の偶奇が必要な情報だったので、それを求めるためにLucasの定理が使用されています。
(p=2としている)
例えば、C(7,2)の偶奇を求める際は(n=5, k=2)
7\ → 111\\
2\ → 010
とまずnとkを二進数に変換してから、
その各桁についてC(n,k)を求め、求めたC(n,k)を掛け合わせます。
C(1,0)*C(1,1)*C(1,0) = 1*1*1 = 1
よってC(7,2)を2で割った余りは1と導出でき、奇数であることがわかります。
実装
実装自体はそんなに難しくありませんが、コンテスト中にやれと言われると手間なので、今後使えるように実装しておきました。
(間違いあれば指摘お願いします)
from scipy.special import comb
# xをn進法表記に変換する関数
def n_ary(x, n):
nums = '0123456789ABCDEF'
result = ''
while(1):
result = nums[int(x % n)] + result
x = x // n
if x==0:
break
return result
# C(n,k)をpで割った余りを返す関数
def lucas(n, k, p):
# nとkをp進法で表記
n_p = n_ary(n, p)
k_p = n_ary(k, p)
# n_pとk_pの桁を揃える(左側を0で埋める)
k_p = k_p.zfill(len(n_p))
result = 1
for n_i, k_i in zip(n_p, k_p):
result *= comb(int(n_i), int(k_i), exact=True)
return result
まとめ
コンテストを終えて、解答を見たとき、「思いつくわけない」と感じました。
しかし、その後解説動画を見ていると、
- ある程度やってる方なら知ってると思いますが〜
- よくあるやり方ですが〜
みたいなフレーズを解説者が言っていて、自分の知識不足を知らされました。
ヒラメキの力に問題があるのかもしれませんが、その前に知識面が不足していると痛感したので、ヒラメキ面については知識が整ってから悩むことにしました。
(今回でいうとパスカルの三角形っぽいものが出てきた時点で二項係数絡みと考えなければならなかった)
次のGrand Contestでは2完できるように知識面の補強をしていこうと思います。