keycards - カードキー (Keycards) Editorial by Mitsubachi
穴の候補を穴 $1,2,3, \cdots ,N$ とし、 $M = 10^9+7$ とします。
穴の開いている位置を決めた時、条件を満たすような鍵の組み合わせは穴の個数のみに依存します。言い換えると穴の個数が同じなら組み合わせの数は同じです。
よって、答えは穴 $1,2,3, \cdots ,K$ のみが開くような鍵の組み合わせに ${}_N C {}_K$ をかけたものです。前者を求めることを考えます。
穴 $1,2,3, \cdots ,K$ が開くということは全ての鍵において穴 $1,2,3, \cdots ,K$ が開いています。よって、穴 $1,2,3, \cdots ,K$ を含む穴の選び方全てにおける鍵の組み合わせを足し合わせた合計は $2^{2^{N-K}}-1$ 通りあります。
ここで、幇助原理の考えを使うことで答えは以下のように表すことができます。
$\sum_{i=0}^{N-K}\ (-1)^i {}_{N-K}C {}_{i} (2^{2^{N-K-i}}-1)$
フェルマーの小定理より $2^{M-1} \equiv 1 ( \mathrm{mod}\ M)$ であり、これを利用することで $2^{2^{N-K-i}}$ をオーバーフローの心配なく計算できます。
具体例を用いて感覚を説明します。
穴 $1$ が開くような鍵の選び方は $2^8-1=255$ 通りあります。しかし、この選び方には穴 $1$ 以外も開くような選び方を含んでおり、これを引かなければなりません。
これらより、穴 $1$ のみが開くような鍵の選び方は $255 \times 1 - 15 \times 3 + 3 \times 3 - 1 \times 1 = 218$ 通りとなります。
直感的には求めたいものとその他の合計を求めます。するとその他を引けばいいので、別のもので引きます。すると、求めたいものから余計に引いた分が生じるので、これを再び足し合わせるために、余計に引いた分と追加の分を足し合わせるといった足し引きを繰り返すようなイメージです。幇助原理について
$N=4,K=1$ の時を考えてみましょう。すなわち穴 $1$ のみが開くような鍵の選び方を考えてみます。
穴 $1,2$ が開くようなもの、 $1,3$ が開くようなもの、 $1,4$ が開くようなものは全て $15$ 通りです。これらを引いた場合、穴 $1,2,3$ が開くようなもの、 $1,2,4$ が開くようなもの、 $1,3,4$ が開くようなものを余計に $1$ 回引いているので、これらを足します。各 $3$ 通りなので、ここでは $9$ を足します。
ここで、穴 $1,2,3,4$ が開くようなものを余計に足しているのでこの $1$ 通りを引きます。
posted:
last update: