ACC2016 24日目「色塗り２」解説

競プロ

Advent Calendar Contest 2016 24日目の問題「色塗り２」を出題させていただいたので、その解説
問題はこちら。

解説
まずは「葉が b 個根に付いた根付き木の頂点を c 色で塗り分ける場合の数」を考えてみます。
コラム
根付き木の同型性に関して扱うときの常套テクとして、各子に何らかの順序をつけてソートすることによって標準化をします。
つまり、「葉に塗る色の番号は左から見たときに昇順になっていなければならない」というルールを付けて数え上げることにすると良いです。
そうすることで、重複無く数え上げることができます。
立式をしてみましょう。
よく見るとまんま重複組み合わせですね。
{}_c H_b*c = {}_{c+b-1} C_b*c
_c H_b は葉の塗り分け方、 *c は根の塗り方。
元の問題に戻って考えてみます。
「葉が b 個根に付いた根付き木の頂点を c 色で塗り分ける場合の数」を d とします。
すると、元の問題の場合の数は「葉が a 個根に付いた根付き木の葉を d 色、根を c 色で塗り分ける場合の数」と同じです。
式にするとこうなります。
{}_d H_a*c = {}_{d+a-1} C_a*c
dを展開した式はこうなります。
{}_{({}_c H_b*c)} H_a*c
式の計算方法を考えます。
{}_{({}_c H_b*c)} H_a*c の偶奇を求めたいのですが、何も考えずにmod 2で計算してしまうとおかしなことになります。
例えば、 {}_5 C_4 \equiv 0 \ne 1 \equiv {}_1 C_0 という具合です。
さてここで、 {}_x C_y\ mod\ 2 の性質について思いを馳せます。
結論から言うと、 x\&y = y なら 0、そうでないなら 1 です。
パスカルの三角形の偶奇を眺めてみたりすると分かるかもしれません。
ここで重要なのが、y を超えるような2冪数を T としたとき、 x\&y = (x\%T)\&y であることです。
つまり、x の正確な値が分かっていなくても、 x\ mod\ T の値さえ分かっていれば {}_x C_y\ mod\ 2 が計算できます。
a \lt 2^{20} なので、 {}_c H_b*c\ mod\ 2^{20} が求められれば良いことになりました。
あとは剰余演算に慣れた人ならそれほど難しくありません。
剰余演算パート
{}_c H_b*c\ mod\ 2^{20} の求め方を考えます。
{}_c H_b = {}_(c+b-1) C_b = (c+b-1)!/b!/(c-1)! なので、階乗どうしの割り算が出来れば良いです。
階乗は前計算しておけばいいのですが、そのまま計算すると割り算で詰むので、工夫が必要です。
値を「奇数*(2冪)」という形に分解し、「奇数」と「指数の肩」の組 (O,E) を計算しておきます。
すると x/y = O_x/O_y*2^{E_x-E_y} という形で計算ができます。
残る問題は奇数での割り算ですが、一般にmodの値と互いに素な数には逆元が存在するため割り算が可能です。
xのmod mでの逆元は x^{\phi(m)-1} と計算できます。
\phi(m) はオイラー関数（mと互いに素なm以下の整数の個数）で、 \phi(2^{20}) = 2^{19} です。
詳しくは蟻本を読むと良いでしょう。更に詳しくは群論とかの本を読むといいかも。
おまけ
元ネタ
KUPC2016のI問題「色塗り」で、本番でそのままmodで計算していってもいいのか考えて、mod 2だとダメだよなぁと思ったのがこの問題を作ったきっかけです。
mod 10億7だとコンビネーションの分母がmodと互いに素になるのでOKっぽい。
発展課題
この問題ではmod 2までで諦めてしまいましたが、 {}_x C_y\ mod\ 2^z を高速で計算できたりしませんかね？→sigma氏からnCm mod 素べきの計算法の論文を教えてもらいました

open all / close all
generated by indenter