Keycards(カードキー) - joi2011-day2 解説

筆者: qnighy

「穴」の集合Nの冪集合である「キーカード」の集合2^Nがあるとき、「キーカードの組み合わせ」の集合2^2^Nのうちその要素の積集合の個数がKであるようなものの数え上げである。

部分点解法

省略

O(NlogN)解法

(logNは逆元を求めるためのものであり、他の本質的な部分はO(N)である。)

問題の整理

まず、この問題では、「1枚も受け取らなかった」場合を数えないことにしている。これは数学的には対称性が悪く、扱いづらいので、この場合は「全ての穴が空いていた」状態として数えることにする。(すなわち、N=Kの場合は、最後に1を引けばよい。)

K個の穴が共通して開いている場合を考えたいが、これをまず開いている穴の組み合わせによって分類してみよう。

すると、開いている穴の組み合わせはnCkあるので、開いている穴の組み合わせを固定した場合の数を求めてからnCk倍すれば答えが得られることがわかる。

残りn-k個の穴についての考察

ここで、残りr=n-k個の穴(開いていてはいけない穴)に注目してみよう。

ここではr=3とし、これらの穴をA,B,Cとおく。

求めたい場合は、[Aが開いていない場合]∩[Bが開いていない場合]∩[Cが開いていない場合]の個数である。

これは、包除原理より、

[すべての場合]-[Aが開いている場合]-[Bが開いている場合]-[Cが開いている場合][AとBが開いている場合][BとCが開いている場合]+[CとAが開いている場合]-[AもBもCも開いている場合]

で計算できる。

包除原理を適用した式の計算方法

i個の穴が開いているカードキーは2^(r-i)枚あるので、i個の穴が開いているようなカードキーの組み合わせは2^2^(r-i)個ある。

同じ個数の穴が開いている場合を纏めて考えると、

Σ(i←0…r) rCi × 2^2^(r-i) × (-1)^(r-i)

を求めればいいことがわかる。

コンビネーションの計算

ここで、コンビネーションを上手に計算することが必要になる。

この場合、コンビネーションを線形で計算する必要があるので、

• nC0 = 1
• nC(k+1) = nCk * (n-k) / (k+1)

の漸化式を用いてrCxを予め全て計算しておくのがよい。

逆元の計算

これを求めるためにmod pにおける逆元(invmod)を求めることが必要になるが、これには

• a^(p-2) ≡ p^-1 (mod p)を用いた方法
• 拡張ユークリッドの互除法extgcd(a,p)を用いて不定方程式ax+py=gcd(a,p)=1を解く方法

の2通りがよく知られており、前者は一回log(p)、後者は一回log(a)で求めることができる。

以上の方法を実装することで満点が獲得できる。