実用・二項係数

TL;DR

\binom{n}{k}

n\k -4 -3 -2 -1 0 1 2 3 4
-4 1 0 0 0 1 -4 10 -20 35
-3 -3 1 0 0 1 -3 6 -10 15
-2 3 -2 1 0 1 -2 3 -4 5
-1 -1 1 -1 1 1 -1 1 -1 1
0 0 0 0 0 1 0 0 0 0
1 0 0 0 0 1 1 0 0 0
2 0 0 0 0 1 2 1 0 0
3 0 0 0 0 1 3 3 1 0
4 0 0 0 0 1 4 6 4 1

主な対象読者

重複組合せ \def\multichoose#1#2{\left(\kern-.3em\left(\genfrac{}{}{0pt}{}{#1}{#2}\right)\kern-.3em\right)}\multichoose{0}{0} を計算しようとしてやらかしたことがある人．

みんな納得すること

n \in \mathbb{Z},\, k \in \mathbb{Z}_{\ge0} のとき， \binom{n}{k} = [x^k] (1+x)^n = \frac{n(n-1) \cdots (n-k+1)}{k!} ということでよいと思います．

流儀 1

k \in \mathbb{Z}_{\lt0} のとき (1+x)^n の k 次の項なんてものはないので， \binom{n}{k} = 0 としてしまうのはありかもしれません．こうすると，二項係数の基本的な性質は以下のようになります：

  • \binom{n}{k} = \binom{n}{n-k} は n \in \mathbb{Z}_{\lt0} では必ずしも成り立たない
  • \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} はすべての n, k \in \mathbb{Z} で成り立つ (これは (1+x)^n = (1+x)^{n-1} (1+x) から直ちに従います)

流儀 2

\multichoose{n}{k} = \binom{n+k-1}{k} を \binom{k+n-1}{n-1} にしたいことはしばしばあると思います．これをすると n, k \in \mathbb{Z}_{\ge0} では (n, k) = (0, 0) のときだけ \binom{-1}{-1} になって大変です．確かに \binom{n}{k} は k と n-k について対称であってほしい感じがあるので，そういう方向で決めていくと， n \in \mathbb{Z}_{\lt0},\, k \in \mathbb{Z} に対して，

  • k \ge 0 のとき \binom{n}{k} = (-1)^k \binom{-n+k-1}{k}
  • n-k \ge 0 のとき \binom{n}{k} = (-1)^{n-k} \binom{-k-1}{n-k}

とするのがよさそうです．間の n \lt k \lt 0 ですが，全部 0 にすると以下を満たすことがわかり，都合がよさそうです：

  • \binom{n}{k} = \binom{n}{n-k} が n \in \mathbb{Z}_{\lt0} はすべての n, k \in \mathbb{Z} で成り立つ
  • \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} は (n, k) = (0, 0) を除くすべての n, k \in \mathbb{Z} で成り立つ

\binom{-1}{-1} = 1 を要請する時点でこの例外はやむを得ません．二項係数の式変形で \binom{0}{0} \ne \binom{-1}{-1} + \binom{-1}{0} にだけ注意すればよいのは，符号をいちいち気にするよりは楽かもしれません．

※追記 (2021/06/24) k \binom{n}{k} = n \binom{n-1}{k-1} もすべての n, k \in \mathbb{Z} で成り立ちます．この式は個人的には \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} の形が覚えやすいです．

お気持ち

a \in \mathbb{Z}_{\lt0} に対し \frac{1}{a!} = 0 であると考えることがよくあります (例えば [1] の Chapter 1 の演習問題など)．これで n, k \in \mathbb{Z}_{\ge0} のときは \binom{n}{k} = \frac{n!}{k! (n-k)!} がある意味正しくなります．

負整数の階乗が分子に来る場合は，分母と打ち消しあって有限の比になるように考えます． \frac{8!}{5!} = 8 \cdot 7 \cdot 6 であるかのように， \frac{(-5)!}{(-8)!} = (-5) \cdot (-6) \cdot (-7) みたいにすると，流儀 2 がこれで上手く説明できます．

ここでは「それっぽい」ことを雰囲気で書きました．ちゃんとやるなら \binom{n}{k} = \frac{\Gamma(n+1)}{\Gamma(k+1) \Gamma(n-k+1)} によってガンマ関数の特異点以外は n, k \in \mathbb{C} で定義できて，それを n \in \mathbb{Z}_{\lt0},\, k \in \mathbb{C} \setminus \mathbb{Z} な点以外で連続になるようにすると，流儀 2 で定めたような値になるようです ([2])．Wolfram 言語の Binomial はそういう複素関数として計算してくれます．

参考文献

[1] Stanley, Richard P. "Enumerative Combinatorics Volume 1 second edition." Cambridge studies in advanced mathematics (2011).

[2] Weisstein, Eric W. "Binomial Coefficient." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BinomialCoefficient.html

Xmas Contest 2020

Xmas Contest 2020

Xmas Contest 2020 にご参加いただいた皆様，どうもありがとうございました！

大変遅くなりましたが解説記事が準備できました．略解を AtCoder 上に載せて一息ついたのもあって 2019 よりもさらに遅くなってしまいました……．その分濃い情報を提供できているつもりなのでお許しください．

今回は，どうやら難易度がかなり高めだったようです．maroon さんはわたしの問題を (実装込みで) かなりの速度で解いていっていたので，ちょっと難しめだけど大丈夫かなと思っていました……．また例年にも増して海外の方が多く参加していただき (日本語問題文しかないのに) ありがたい限りです．ちなみにわたしも最近中国語のコンテストにたまに出ています．

わたしが原案を出した問題の解説はこちらです．

それ以外の問題との対戦結果は以下になります．こちらも解法ネタバレを含みます．

続きを読む

Xmas Contest 2020 I: Implement Me 解説

Xmas Contest 2020

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_i

問題概要

F(x_0, \ldots, x_{M-1}) は， x_0, \ldots, x_{M-1} のうち 1 が L 個以上なら 0 で， L 個未満なら 1 である．この F だけを使って与えられた関数 G\colon \{0, 1\}^N \to \{0, 1\} が作れるか判定し，作れる場合は実装せよ．

簡単な場合

部分点が N \le 2 についています．この部分点自体は 2^{2^N} 通りのうち作れる関数をすべて探索することで獲得できるのですが， M や N が小さい場合について考察してみましょう．

M = 1 のときは F は NOT です F(x_0) = \overline{x_0}．このときは G の入力の変数 y_i いずれかの否定 \overline{y_i} とそのまま \overline{\overline{y_i}} = y_i 以外はどうがんばっても作れません．実はこの場合はコーナーケースであることが後々発覚するので場合分けします．

M = 2 のときは， L = 1 ならサンプルにあるように F は NOR， L = 2 なら F は NAND になっています．リンク先 Wikipedia にもありますが，NOR や NAND はそれ 1 つで任意のブール関数を作れる (完全である) ことがよく知られています．具体的には，NOR の場合は \overline{x} = (x \mathbin{\mathrm{NOR}} x)， (x_0 \mathbin{\mathrm{OR}} x_1) = \overline{x_0 \mathbin{\mathrm{NOR}} x_1}， (x_0 \mathbin{\mathrm{AND}} x_1) = (\overline{x_0} \mathbin{\mathrm{NOR}} \overline{x_1}) のように NOT, OR, AND が，適当な変数をとって 0 = (y_i \mathbin{\mathrm{NOR}} \overline{y_i})， 1 = \overline{0} によって定数が得られて (NAND の場合も同様)， G(y_0, \ldots, y_{N-1}) = \bigvee_{(y'_0, \ldots, y'_{N-1}) \in G^{-1}(1)} \bigwedge_{i=0}^{N-1} [y_i = y'_i] のように書くと G も作れることがわかります (例えばサンプルの場合は (y_0 \mathbin{\mathrm{AND}} \overline{y_1} \mathbin{\mathrm{AND}} y_2) \mathbin{\mathrm{OR}} (y_0 \mathbin{\mathrm{AND}} y_1 \mathbin{\mathrm{AND}} y_2) とします)．

一方， N = 1 のときは，とりあえず最初にできることは F(y_0, \ldots, y_0) しかなくてこれは \overline{y_0} です．次にできるのは y_0 と \overline{y_0} を何個かずつ入れることですが，片方だけ L 個以上だと y_0 か \overline{y_0} になってしまうので意味なく，「両方を L 個以上」または「両方を L 個未満」にすることで定数 0 または 1 が得られます (片方を得ればもう片方も得られます)．が，これは ( M が奇数で) L = \frac{M+1}{2} のときだけできません！　これが特殊な場合になることがわかります． N = 1 だとこれ以上どうすることもできません．

考察

上の考察を合わせる感じにすると， 2 個の値 x, x' を適切な個数選んで入れれば便利なものが作れそうです．具体的には，

  • L \lt \frac{M+1}{2} のときは， L \le \left\lfloor\frac{M}{2}\right\rfloor なので，例えば x を \left\lfloor\frac{M}{2}\right\rfloor 個， x' を \left\lceil\frac{M}{2}\right\rceil 個とすると，両方 L 個以上なので F(x, \ldots, x, x', \ldots, x') = (x \mathbin{\mathrm{NOR}} x')，
  • L \gt \frac{M+1}{2} のときは， L \gt \left\lceil\frac{M}{2}\right\rceil なので，例えば x を \left\lfloor\frac{M}{2}\right\rfloor 個， x' を \left\lceil\frac{M}{2}\right\rceil 個とすると，両方 L 個未満なので F(x, \ldots, x, x', \ldots, x') = (x \mathbin{\mathrm{NAND}} x')

となります．あとはこれを使って M = 2 の考察に書いたように任意のブール関数が実現できます．NOT, OR, AND をとるのに定数回の F の使用がかかるので，全体で F を O(2^N N) 回使うことになります．これで 10^4 行制限は多少の無駄があっても大丈夫だと思いますが， F の使用を O(2^N) 回にすることも一応できます：各 k = 0, \ldots, N と (y'_0, \ldots, y'_{k-1}) \in \{0, 1\}^k に対し \bigwedge_{i=0}^{k-1} [y_i = y'_i] を順に求めていけばよいです (論理決定の二分木を根のほうから作っていくイメージ)．

特殊な場合

さてコーナーケースということにしていた L = \frac{M+1}{2} のときですが，これがこの問題の難しいところです．入力の変数いずれかの否定 F(y_i, \ldots, y_i) = \overline{y_i} かそのまま \overline{\overline{y_i}} = y_i はとりあえず作れて， N \le 2 のときは実はこれ以外は作れないことが以降の議論でわかります．これを予想して実装すると 20 点の部分点となります．

では， G が作れるための必要条件を考えましょう． x_0, \ldots, x_{M-1} のうち 1 が \frac{M+1}{2} 個以上というのは， 0 が M - \frac{M+1}{2} = \frac{M-1}{2} 個以下，すなわち \frac{M+1}{2} 個未満であることと同値です．この対称性に着目すると， F(\overline{x_0}, \ldots, \overline{x_{M-1}}) = \overline{F(x_0, \ldots, x_{M-1})} であることがわかります．つまり，入力の変数の 0/1 をすべて反転させると出力も反転するということです．この性質は F だけを使って作れるすべての関数に伝搬するので， G(\overline{y_0}, \ldots, \overline{y_{N-1}}) = \overline{G(y_0, \ldots, y_{N-1})} が必要条件となることがわかりました．

そして，この条件を満たす G はなんとすべて作ることができます．( N \ge 1 なので，) G(\overline{y_0}, \ldots, \overline{y_{N-2}}, 1) = \overline{G(\overline{y_0}, \ldots, \overline{y_{N-2}}, 0)} が成り立つため， y_{N-1} = 0 のときに正しく G を計算する関数が F だけで作れていれば， y_{N-1} = 1 のときも自動的に正しいということになります (!)．ということは， y_{N-1} が定数 0 だと思って構成してよいということになります (!!)．

定数 0 を得てしまえばあとはいろいろな方法があって，例えば F を F(x_0, \ldots, x_{M-2}, 0) のようにすると M が 1 小さい場合に帰着されて，特殊な場合ではなくなり (ここが M = 1 を最初に処理した理由です)， y_0, \ldots, y_{N-2} のすべての関数を作ることができます．

背景

Post's lattice というものがあります．この束の各元は，合成 (と射影) について閉じたブール関数の集合，別の言い方をすれば「組み合わせて作った関数にも伝搬する性質」を表しています．このなかでも最大元 \top を除いたときの極大元 M, D, A, P_0, P_1 が重要で，これは (この問題の形に限らない) ブール関数 F\colon \{0, 1\}^M \to \{0, 1\} についての以下の性質をそれぞれ表します：

  • M (monotone)： x_0 \le x'_0,\, \ldots,\, x_{M-1} \le x'_{M-1} ならば F(x_0, \ldots, x_{M-1}) \le F(x'_0, \ldots, x'_{M-1})
  • D (self-dual)： F(\overline{x_0}, \ldots, \overline{x_{M-1}}) = \overline{F(x_0, \ldots, x_{M-1})}
  • A (affine)：ある a_0, \ldots, a_{M-1}, b \in \{0, 1\} が存在して， F(x_0, \ldots, x_{M-1}) \equiv a_0 x_0 + \cdots + a_{M-1} x_{M-1} + b \pmod{2}
  • P_0 ( 0-preserving)： F(0, \ldots, 0) = 0
  • P_1 ( 1-preserving)： F(1, \ldots, 1) = 1

つまり， F がこれらのいずれかの性質を持っていたら F から作れる関数もその性質を持ち，一方 F がこれらのいずれをも持っていなかったら F だけですべてのブール関数が作れる，ということが知られています．

今回の問題では， M \ge 2 として， L = \frac{M+1}{2} のときは F が D に属すが M, A, P_0, P_1 に属さないので D に属するすべての関数が作れて，そうでないときは F が M, D, A, P_0, P_1 のいずれにも属さないのですべての関数が作れる，ということになります．わたしは不勉強で Post's lattice の導出を知らないのですが，束の構造の証明から具体的な構成方法も得られるのかもしれません (ご存じの方は教えてください！)．

統計情報

正解者：tomerun さん (2:45:27) はじめ 2 チーム

コメント

majority 関数を想像しつつ monotone でなくなるように適当に変えてみました．すべてのブール関数が作れるかの判定法を知っていたのでずるではあるのですが，構成方法を思いついてみると L = \frac{M+1}{2} の場合がとても面白かったので問題になりました．構築問題としても見慣れない雰囲気があって (ありますよね？)，なんだか騙されたような感じがしますね．

Xmas Contest 2020 H: Hierarchical Phylogeny 解説

Xmas Contest 2020

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_h

問題概要

頂点に \{0, \ldots, N-1\} の空でない部分集合のラベルがついた根付き木であって，各頂点が

  • 子が 0 個で，ラベルが指定された部分集合 ( L) のいずれか
  • 子が 2 個で，ラベルが子のラベルの非交和

のいずれかであるようなもののうち，根のラベルが指定された部分集合 ( R) のいずれかであるようなものの個数を \operatorname{mod} 998244353 で求めよ．

立式

\{0, \ldots, N-1\} の部分集合全体を \mathcal{P} とします．入力の L を \mathcal{P} 上の関数として表しておきます ( A \in \mathcal{P} が葉にふさわしいとき L(A) = 1，そうでないとき L(A) = 0)．

入力の R でいろいろ指定されていますが，結局，根のラベルを指定したときの木の個数を求められればよいです． A \in \mathcal{P} に対し， f(A) を条件を満たす木であって根のラベルが A であるものの個数とします ( f(\emptyset) = 0 です)．根の子の個数が 0 か 2 かで場合分けして，漸化式 f(A) = L(A) + \frac12 \sum_{B\sqcup C=A} f(B) f(C) が従います ( \sqcup で非交和を表すことにします)．係数 \frac12 は子の順番を区別しないためのものです．これをそのまま DP すると O(3^N) 時間になります．

subset convolution

g, h\colon \mathcal{P} \to \mathbb{C} に対して，それらの subset convolution g * h\colon \mathcal{P} \to \mathbb{C} は (g * h)(A) = \sum_{B\sqcup C=A} g(B) h(C) で定義されます．この解説では単に積のように g h と書いてしまうことにします．代数の言葉で書くと，和を各点での和，積を subset convolution とすることで \mathcal{P} から \mathbb{C} への関数全体が環となります．乗法の単位元は 1(\emptyset) = 1， 1(A) = 0 ( A \ne \emptyset) なる 1 です．

subset convolution は O(2^N N^2) 時間で計算できることが知られています [1]．論文を読んでいただくのがいいと思うのですが，ここでもアルゴリズムを簡単に説明しておきます．メインアイデアは B \sqcup C = A が「 B \cup C = A かつ \lvert B \rvert + \lvert C \rvert = \lvert A \rvert」と同値ということの利用で，集合のサイズの情報を持たせておいてから \cup についての畳み込み (累積和→積→差分) をします．すなわち g に対し \hat{g}\colon \mathcal{P} \to \mathbb{C}[z] を \hat{g}(A) = \sum_{B\subseteq A} g(B) z^{\lvert B\rvert} で定め， \hat{h} も同様にし，これらの各点積 (多項式の積) を計算し \hat{k}(A) = \hat{g}(A) \hat{h}(A)，Möbius 変換で戻し k(A) = \sum_{B\subseteq A} (-1)^{\lvert A\setminus B\rvert} \hat{k}(B)，集合のサイズと次数が合っているところをとればよいです (gh)(A) = [z^{\lvert A\rvert}] k(A)．多項式の積は \operatorname{mod} z^{N+1} で計算すれば十分です (さらに細かくいうと \hat{k}(A) は \operatorname{mod} z^{\lvert A\rvert+1} で合っていればよいです ※追記 これ普通に嘘です 例を見てください)．

一応例もやっておきます． N = 2 として， \mathcal{P} 上の関数は (入力形式のように) \emptyset, \{0\}, \{1\}, \{0, 1\} の行き先の列で書くことにします．

  1. g = (1, 2, 3, 4),\, h = (5, 6, 7, 8) とする
  2. 集合のサイズの情報を持たせると (1, 2z, 3z, 4z^2), (5, 6z, 7z, 8z^2)
  3. 累積和をとって (いわゆるゼータ変換) \hat{g} = (1, 1+2z, 1+3z, 1+5z+4z^2),\, \hat{h} = (5, 5+6z, 5+7z, 5+13z+8z^2)
  4. 各点積をとって \hat{k} = (5, 5+16z+12z^2, 5+22z+21z^2, 5+38z+93z^2+92z^3+32z^4)
  5. 差分をとって (Möbius 変換) k = (5, 16z+12z^2, 22z+21z^2, 60z^2+92z^3+32z^4)
  6. サイズが合っているところをとる g h = (5, 16, 22, 60)

さて，subset convolution は 2 個以外の積の場合も同様です (各点積をとるときに個数が変わるだけです)．また \hat{} をつけたりとったりする操作は線型性を持っています．つまり例えば 5 g + 8 g^2 h を求めたければ \hat{g}, \hat{h} を求めてから 5 \hat{g}(A) + 8 \hat{g}(A)^2 \hat{h}(A) を計算して変換を戻せばよいです．このように，多項式 \phi に対し， \phi(g) を計算するには各多項式 \phi(\hat{g}(A)) を求めればよいことになります．この多項式計算がそれぞれ O(N^2) 時間でできれば全体で O(2^N N^2) 時間となります．

sqrt

元の問題に戻りましょう． f(A) = L(A) + \frac12 \sum_{B\sqcup C=A} f(B) f(C) は f = L + \frac12 f^2 と書けます．これを f = 1 \pm \sqrt{1 - 2 L} のように解けたらよさそうなので，正当化します．

L(\emptyset) = 0 なので，subset convolution の定義を考えて L^{N+1} = 0 です．冪級数展開 \sqrt{1 + x} = \sum_{i\ge0} \binom{1/2}{i} x^i = 1 + \frac{1}{2} x - \frac{1}{8} x^2 + \cdots に倣って g = \sum_{i=0}^N \binom{1/2}{i} (-2L)^i と定めると， g^2 を計算したとき高次の項が消えて， g^2 = 1 - 2 L がわかります． g^2 = 1 - 2 L なる g がこれかこれの -1 倍しかないことは小さい部分集合から順番に値が決まっていくことから示せます．よって g(\emptyset) = 1 なる方を \sqrt{1 - 2 L} と書けて， f(\emptyset) = 0 と合わせて f = 1 - \sqrt{1 - 2 L} と求めたいものが書けました．

さて，あとは多項式 \hat{L}(A) に対して \sum_{i=0}^N \binom{1/2}{i} (-2\hat{L}(A))^i を計算できればよくなりました．これは形式的冪級数としての \sqrt{1 - 2 \hat{L}(A)} を \operatorname{mod} z^{N+1} で計算できればよく，それは低次の項から順番に合わせれば O(N^2) 時間でできます．なお，説明の簡単のために値を \mathbb{C} で考えましたが，今回は 2 でしか割っていません (sqrt の代わりに exp 等が登場すると 1, \ldots, N の逆数が要ります)．

実装

\Theta(3^N) を落とさなければいけない都合上 O(2^N N^2) でも定数倍が幾分厳しめな時間制限設定になってしまっています．準備陣想定解のうち速いものは 1.5 秒程度 (C++, D)， \Theta(3^N) のものは 12 秒程度 (C++) でした．想定解の場合は以下のような注意点が挙げられます：

  • 高々 N 次の多項式を 2^N 個持つので 2 次元配列を使うことになりますが，sqrt の計算が支配的なので，C++ などでいう [2^N][N+1] の順番のほうが [N+1][2^N] の順番より速くなるはずです．
  • 形式的冪級数の sqrt は O(N \log N) 時間でできますが，今回は N が小さいので定数倍が非常に痛く向いていません．
  • sqrt をとるとき log をとって \frac12 倍して exp するのは定数倍が大きく間に合わないかもしれません．log を介さず累乗を O(N^2) で行う方法 (微分の利用) だとちょっとだけ遅いですが間に合います．
  • sqrt を低次の項から合わせるとき対称性を使って掛け算の回数を約半分にできます．これは必須ではありませんが結構効いてきます．
  • 配列を静的に確保すると速くなります．なお，Java の 2 次元配列で動的に確保して 6 秒にぎりぎり間に合うくらいでした．

別解

heno239 さんのアイデアが，subset convolution を中身をいじらずに用いる方法でした．

リンク先 Twitter を見ていただきたいのですが，dp2 として「条件を満たす木において葉の 1 個に印をつけたもの」を数えています．これを一緒に計算することで， \{0, \ldots, N-1\} の元を 1 個特別にとって再帰的に解くことができています．畳み込み方としてはいわゆる分割統治 FFT の気持ちにちょっと似ているかもしれません．

代数的には一体何が起こっているのかというのを補足しておきます． t\colon \mathcal{P} \to \mathbb{C} を t(\{N-1\}) = 1， t(A) = 0 ( A \ne \{N-1\}) で定めて L = L_0 + L_1 t,\, f = f_0 + f_1 t と書けます ( N-1 \in A のとき L_0(A) = L_1(A) = f_0(A) = f_1(A) = 0)． f = L + \frac12 f^2 を展開して， t^2 = 0 に注意すると， f_0 = L_0 + \frac12 f_0^2 および f_1 = \frac{L_1}{1 - f_0} が得られます．前者は DP 配列の前半が再帰的に計算できることを言っています．後者は DP 配列の後半を求めるために \frac{1}{1 - f} もほしいということを言っています． g = \frac{1}{1-f} とおいて (これが dp2 です) 同様に g = g_0 + g_1 t と書くと， (1 - f) g = 1 から g_0 = \frac{1}{1 - f_0} および g_1 = \frac{f_1 g_0}{1 - f_0} = f_1 g_0^2 が得られます．これで f_1, g_1 を L_1, g_0 から求めることができました．一般に \phi(f) = 0 を解くときは \phi(f_0) + \phi'(f_0) f_1 t = 0 となり，これはつまり Newton 法の一種です．

subset convolution を中身をいじらず，とは言いましたが， O(2^N N^2) 時間ではあるもののちょっと定数倍が重く残念ながら TLE になってしまったようです．いろいろ試してみたのですが，同じ列に対するゼータ変換・Möbius 変換を複数回行わないようにすることでなんとか通せるかもしれないというくらいでした．ちなみに，この解法には 2 による割り算すら登場しません．

統計情報

正解者：チーム iwiwi (0:49:32) はじめ 4 チーム

コメント

高度典型です！

特に中国で元々有名だった手法です．あまりちゃんと調査を行っていないのですが，中国の IOI 選抜に使われる論文 [2] がこの手の応用のおそらくきっかけです．中国語で「子集卷积」 (subset convolution) やら「集合幂级数」 (set power series) やらを検索することで情報がわんさか出てきますね．日本で話題になったのは ARC 105 のときで，Elegia さんの書き込みのおかげで知れ渡る形となりました．

問題としては解法ドリブンみたいな作問ですが，そこそこ自然な設定で解けた・sqrt は例題が全然見当たらなかったので，日頃からアンテナを張ってる方々へのボーナスという気持ちも込めて出題しました．普段のコンテストだとそもそも計算量の区別でも不幸を呼びやすく出しにくいですし，クリスマスということで．

参考文献

[1] Björklund, Andreas, et al. "Fourier meets Möbius: fast subset convolution." Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. 2007.

[2] 吕凯风. "集合幂级数的性质与应用及其快速算法." 2015年信息学奥林匹克中国国家队候选队员论文. 2015.

Xmas Contest 2020 G: Graph Products 解説

Xmas Contest 2020

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_g

問題概要

無向単純グラフ H, H' に対し，"Cartesian product" H \mathbin{\square} H' と "tensor product" H \times H' が同型か判定せよ．

考察

サンプルは全然あてになりません．クリスマスだから許されている (許されていますか？) 無みたいなサンプルシリーズも久しぶりですね (2010 G, 2012 D, 2014 C)．

小さいグラフで同型になるものを探してみると，まずは H, H' が 1 点というのがありますね．そして孤立点が複数並んでいても同型です．もうちょっと探すと H, H' ともに三角形にすると同型になることが見つかるかもしれません (図を書いてみてもそんなに明らかではないと思います)．三角形がいくつか並んでいるもの同士でも OK です．

辺の数に着目するというのも思いつきやすい考察だと思います． N M' + M N' = 2 M M'，したがって (N - M) M' + M (N' - M') = 0 のような式が得られます．これだけで直接嬉しいことはなさそうですが， N = M のグラフが怪しいというヒントにはなるかもしれません．

結論

a \ge 3 に対し， a 頂点の閉路を C_a と書きます．

結論を述べると， H \mathbin{\square} H' と H \times H' が同型であるための必要十分条件は，以下のいずれかを満たすことです：

  1. H も H' もすべての頂点が孤立点である (辺がない)．
  2. ある奇数 a \ge 3 が存在して， H も H' もすべての連結成分が C_a である．

これは線型時間で判定できます．元の問題も，各グラフについて前計算することで入力について線型時間でできます．

十分性

1. の場合は，頂点数が等しくて辺がないので同型です．

2. の場合を考えます． H の連結成分と H' の連結成分の組それぞれに対し， H \mathbin{\square} H' および H \times H' に対応する C_a \mathbin{\square} C_a および C_a \times C_a が (誘導部分グラフとして) 含まれるので，結局 C_a \mathbin{\square} C_a と C_a \times C_a が同型であることを示せばよいです．

C_a の頂点集合を \mathbb{Z}/a\mathbb{Z} とみなし， u, v \in \mathbb{Z}/a\mathbb{Z} を結ぶ辺があることを v - u = \pm 1 と同値であるようにできます ( \operatorname{mod} a で隣り合うものを辺で結ぶということ)．写像 \colon \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/a\mathbb{Z}; (u, u') \mapsto (u + u', u - u') を考えると，逆写像 (v, v') \mapsto \left(\frac{v+v'}{2}, \frac{v-v'}{2}\right) があるので全単射であり， C_a \mathbin{\square} C_a の (u, u') と (u + 1, u') を結ぶ辺， (u, u') と (u, u' + 1) を結ぶ辺を，それぞれ C_a \times C_a の (u + u', u - u') と (u + u' + 1, u - u' + 1) を結ぶ辺， (u + u', u - u') と (u + u' + 1, u - u' - 1) を結ぶ辺に移せるので，そして逆の対応も同様なので・あるいは辺の数が 2 a^2 で等しいので， C_a \mathbin{\square} C_a と C_a \times C_a は同型です．

平たく言えば，図を書いて片方を 45 度回転させてよく見ると同型になっています．足したり引いたりしているところに両方とも同じ \mathbb{Z}/a\mathbb{Z} であることを， 2 で割っているところに a が奇数なことが使われています．

必要性

以下の順で検討します：

  1. 最大次数
  2. 次数
  3. 連結成分の個数
  4. 二部であるような連結成分の個数
  5. 含まれる最小の奇閉路の大きさ

もちろんこれはある程度整理された道筋なので，実際に解くときにこのようにきれいにできるべきという話ではありません．

H \mathbin{\square} H' と H \times H' が同型とします．

1. H の頂点の次数を d_1 \le \cdots \le d_N， H' の頂点の次数を d'_1 \le \cdots \le d'_{N'} とします．すると， H \mathbin{\square} H' の頂点の次数は d_u + d'_{u'} たち， H \times H' の次数は d_u d'_{u'} たちとなります．特に， H \mathbin{\square} H' と H \times H' で最大次数は等しいので， d_N + d'_{N'} = d_N d'_{N'} となります． 1 = (d_N - 1) (d'_{N'} - 1) となるので， (d_N, d'_{N'}) = (0, 0), (2, 2) のみがあり得ます．前者の場合は辺がないのでこれでよいです．以下後者であると仮定します．

2. H に次数 1 の頂点があるとすると， H \mathbin{\square} H' には次数 1 + 2 = 3 の頂点がありますが H \times H' にはなく矛盾します．よって H には次数 1 の頂点がなく， H' も同様です．するとさらに， H に次数 0 の頂点があるとすると， H \mathbin{\square} H には次数 0 + 2 = 2 の頂点がありますが H \times H' にはなく矛盾します．よって H には次数 0 の頂点がなく， H' も同様です．以上より， H, H' ともにすべての頂点の次数が 2 であり，すなわちすべての連結成分が閉路です．

H の連結成分を C_{a_1}, \ldots, C_{a_l}， H' の連結成分を C_{a'_1}, \ldots, C_{a'_{l'}} とすると， H \mathbin{\square} H' は C_{a_i} \mathbin{\square} C_{a'_{i'}} たちを並べたもの， H \times H' は C_{a_i} \times C_{a'_{i'}} たちを並べたものです．

a, a' \ge 3 とします． C_a, C_{a'} の頂点集合を十分性を示したときと同様に \mathbb{Z}/a\mathbb{Z}, \mathbb{Z}/a'\mathbb{Z} とみなし，差が 1 の頂点が辺で結ばれているとします． C_a \mathbin{\square} C_{a'} について，

  • a, a' ともに偶数のとき，連結で，二部である ( (x, y) \in \mathbb{Z}/a\mathbb{Z} \times \mathbb{Z}/a'\mathbb{Z}) に対し ( (x \bmod 2) + (y \bmod 2) ) \bmod 2 が well-defined でこれで二部に塗り分けできる)
  • a, a' の一方のみ奇数のとき，連結で，二部でない ( C_a, C_{a'} を部分グラフとして持つため)
  • a, a' ともに奇数のとき，連結で，二部でない ( C_a, C_{a'} を部分グラフとして持つため)

また， C_a \times C_{a'} について，

  • a, a' ともに偶数のとき，非連結である ( (x, y) \in \mathbb{Z}/a\mathbb{Z} \times \mathbb{Z}/a'\mathbb{Z}) に対し ( (x \bmod 2) + (y \bmod 2) ) \bmod 2 が well-defined で，これで連結成分が分かれる)
  • a, a' の一方のみ奇数のとき，連結で，二部である ( a が奇数として，各頂点から (+1, +1) と (+1, -1) を繰り返し辿ると (+1, 0) ができるので (+1, +1) と合わせて連結． (x, y) に対し y \bmod 2 が well-defined でこれで二部に塗り分けできる)
  • a, a' ともに奇数のとき，連結で，二部でない (上と同様に各頂点から (+1, 0) や (0, +1) ができるので連結．ある頂点から (+1, +1) を繰り返し辿ると C_{\mathrm{lcm}(a,a')} を部分グラフとして持つことがわかるので二部でない)

ということがわかります．

3. C_{a_i} \mathbin{\square} C_{a'_{i'}} はすべて連結なので， H \mathbin{\square} H' の連結成分は l l' 個． H \times H' もそうであるためには C_{a_i} \times C_{a'_{i'}} もすべて連結であることが必要で，よって a_i, a'_{i'} がともに偶数とはなりません．

4. a_i, a'_{i'} がともに偶数とはならないので， C_{a_i} \mathbin{\square} C_{a'_{i'}} はすべて，二部でないです．よって H \mathbin{\square} H' の連結成分はすべて，二部でないです． H \times H' もそうであるためには C_{a_i} \times C_{a'_{i'}} もすべて，二部でないことが必要で，よって a_i, a'_{i'} はすべて奇数です．

5. a, a' \ge 3 を奇数とするとき，

  • C_a \mathbin{\square} C_{a'} が含む最小の奇閉路の大きさは \min\{a, a'\} (閉路に沿って移動した \pm 1 の和がどちらかの成分で奇数なので，どちらかの成分は ( \operatorname{mod} a あるいは \operatorname{mod} a' で) 1 周以上しなければならない． C_{\min\{a, a'\}} を含むのは明らか)
  • C_a \times C_{a'} が含む最小の奇閉路の大きさは \max\{a, a'\} (閉路に沿って移動した \pm 1 の和が両方の成分で奇数なので，両方の成分が 1 周以上しなければならない． C_{\max\{a, a'\}} は， (+1, +1) を \min\{a, a'\} 個と残りを (+1, -1) または (-1, +1) で作れる)

ということがわかります．よって \min\{a_i, a'_{i'}\} たちの多重集合と \max\{a_i, a'_{i'}\} たちの多重集合が等しい必要があります．対応する各元ごとに \le なのですべて等号でなければならず， a_i, a'_{i'} がすべて等しいことが従います．

統計情報

正解者：チーム YdeOgwSasUshPunO (0:52:16) はじめ 12 チーム

コメント

白状すると，わたしは最初異なる奇閉路の積の場合を勘違いしていました…… (嘘の同型を作っていた上に，見直しのときは場合分けが漏れました)．maroon さんに test-solve してもらったときに気づいて，証明を書き直してチェックを受けました．直感が働きにくい問題なので，気を付けましょう．危ないところでした．

Xmas Contest 2020 D: Determinant 解説

Xmas Contest 2020

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_d

問題概要

N \times N 行列 A の (i, j) 成分は

  • i = j のとき 1
  • i \nmid j のとき C
  • i \ne j かつ i \mid j のとき 0

である． (\det A) \bmod 998244353 を求めよ．

行列式の処理

対角だけ変なことになっているので，対角をどう使うかで場合分けします． 1 = C + (1-C) だと思って，行列式の定義の各項 ( N 個の成分の積) のうちどの対角で 1-C の部分をとるかという場合分けをします．別の言い方をすると， (i, i) 成分に C + x_i が書いてあると思って，行列式を x_1, \ldots, x_N の多項式として書いて各係数を求めるということです．なお，なぜ 1 = 0 + 1 でなく 1 = C + (1-C) なのか (なぜ x_i でなくて C + x_i なのか) は，いろいろ試してみてうまくいくほうを選びましょうというより多くのことは言えなさそうです．

まとめると， A の対角を 1-C に置き換えた行列を B とし， S \subseteq \{1, \ldots, N\} に対し i, j \in S なる成分だけ取り出した行列 (主小行列) を B_S となります． \det A = \sum_{S\subseteq\{1,\ldots,N\}} (1-C)^{N-\lvert S\rvert} \det B_S となります． \det B_S の例を載せます．

\begin{align} B_{\{1, 2, 10, 20, 60\}} &= \begin{bmatrix} C&0&0&0&0 \\ C&C&0&0&0 \\ C&C&C&0&0 \\ C&C&C&C&0 \\ C&C&C&C&C \end{bmatrix}, \\ B_{\{1, 2, 14, 20, 60\}} &= \begin{bmatrix} C&0&0&0&0 \\ C&C&0&0&0 \\ C&C&C&C&C \\ C&C&C&C&0 \\ C&C&C&C&C \end{bmatrix} \end{align}

B_\emptyset = 1 です．ある j \in S があって S の任意の元が j を割り切るとき， j の列が対角だけ C で他が 0 なので， \det B_S = (\det B_{S \setminus \{j\}}) \cdot C となります．そうでないとき， S には整除関係について極大な (つまり，他の S を割り切らない) 相異なる 2 元 i, i' がとれますが， i, i' の行はともに全部 C なので， \det B_S = 0 です．

というわけで S が整除関係について全順序な (つまり，どの 2 元も一方が他方を割り切る) とき \det B_S = C^{\lvert S\rvert}，そうでないとき \det B_S = 0 です．よって，整除関係について全順序であるような \{1, \ldots, N\} の部分集合をその大きさごとに係数をかけて数える問題になりました．

数え上げ

C = 1 のときは S = \{1, \ldots, N\} が全順序かどうかになるので， N \le 2 のとき 1 で N \ge 3 のとき 0 が答えになります．

C \ne 1 のときは r = \frac{C}{1-C} とおいて係数を r^{\lvert S\rvert} とみると考えやすいのでそうします．全順序な S のうち， 1 を含むものと含まないものがちょうど対応するので，片方だけ数えると楽です． F(n) を，整数列 1 = i_0 \lt i_1 \lt \cdots \lt i_k \le n であって i_0 \mid i_1 \mid \cdots \mid i_k なるものについての r^k の和とすると， \det A = (1-C)^N (1+r) F(N) です． k = 0 なものは 1 通りで，そうでないものは i_1 で分類して， 1 = \frac{i_1}{i_1} \lt \cdots \lt \frac{i_k}{i_1} \le \left\lfloor\frac{n}{i_1}\right\rfloor が 1 つ短い列に対応するので，漸化式 F(n) = 1 + r \sum_{i=2}^n F\left(\left\lfloor\frac{n}{i}\right\rfloor\right) が得られます．

これをそのまま DP すると O(N^2) 時間かかりますが， \left\lfloor\frac{n}{i}\right\rfloor が同じ部分をまとめれば O(N^{3/2}) となります (20 点)．さらに， F(N) を求めるのに必要な F(n) は n = \left\lfloor\frac{N}{i}\right\rfloor と書けるもののみであることに注意します．これで計算量を N^{1/2} の前後で分けて評価すると O(N^{3/4}) であることがわかります．これは，Xmas Contes 2019 D 問題と同様なのでこちらで詳しく解説しています．

数え上げ (別解)

上の方法では S の最小元だけ 1 に固定し最大元は動かして考えていましたが，最大元も固定して考えるのも自然かもしれません． f_k(n) を，整数列 1 = i_0 \lt i_1 \lt \cdots \lt i_k = n であって i_0 \mid i_1 \mid \cdots \mid i_k なるものの個数とします． F(N) = \sum_k r^k \sum_{n=1}^N f_k(n) です．

k \ge 1 を固定すると，これは k 個の不等号 \lt の条件を「 \le だが = でない」と読んで包除することで，各素因数について条件が独立になって数えられます．具体的には， n の素因数分解を n = \prod_m p_m^{e_m} として f_k(n) = \sum_{l=1}^k (-1)^{k-l} \binom{k}{l} \prod_m \binom{e_m+l-1}{l-1} です．

これで各 n について計算すれば 20 点です．100 点をとるには，以下のような工夫が考えられます：

  • f_k(n) は入力に依存しないので，累積和を適当な間隔で埋め込む (結構大変だと思います)．
  • f_k(n) は素因数分解の指数の多重集合にしか依存しないので，同じ値を複数回計算しない ( N = 10^9 で 1324 通りになります)．素因数分解の指数の列が同じ n をうまくまとめて数える (詳細は省略しますが，高速素数カウントを用いて最大素因数だけ異なる数をまとめて処理することができます)．

統計情報

正解者：チーム エイシーのチーム (2:22:35)

20 点：3 チーム

コメント

行列式処理ステップも数え上げステップも典型ひとひねり (?) という感じだったかもしれません．一般の半順序集合についても同様の行列式処理ができるのですが，整除関係でやってみると問題文のシンプルさに対して解法や計算量にひねりが生まれるというのが面白かったです．

Xmas Contest 2020 C: Candies Candidates 解説

Xmas Contest 2020

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_c

問題概要

数列中の正の整数 x を x-1 または \left\lfloor\frac{\sqrt{5}-1}{2} x\right\rfloor に変えられるゲームがある．与えられた数列が先手必勝か後手必勝か判定せよ．

とりあえず

値が減っていく不偏ゲームなので (short impartial game なので)，各皿の Grundy 数を考えて XOR をとればよいです．

行動が 2 通りしかないので Grundy 数も高々 2 までしか登場しません．が，これ以上は見て直ちにわかることはないので，実験しましょう．

解法 1 (観察)

実験して出てきた 0, 1, 2 の列をぐっとにらむと，再帰的構造が見えてくるかもしれません．

解法 2 (OEIS)

0, 1, 2 の列を OEIS に入れても出てこない (2020 年 12 月現在) のですが，Grundy 数がそれぞれ 0, 1, 2 になる値の列はなんと出てきます：

これらのタイトル通りに実装すると (あるいは解法 1 でもそうかもしれませんが) 小数計算が必要になります．整数と整数の比は黄金比にかなり近くなりうるので (隣接する Fibonacci 数)， \left(\frac{1 + \sqrt{5}}{2}\right)^2 などを求める時点でかなりの精度が要求されます．Java の BigDecimal や Python の Decimal などを用いて正解できます．

解法 3 (Zeckendorf representation)

よく見ると上の 1 の OEIS にもちらっと書いてあるのですが，Zeckendorf representation，いわゆる Fibonacci 進法を考えるとうまくいきます．任意の非負整数は相異なる隣接しない Fibonacci 数の和の形に一意に表すことができ，その表示は大きいほうから貪欲にとっていくことで求められます．この表示と Grundy 数を並べて出力してみると，以下のことに気づくことができると思います．

  • Grundy 数が 0： 0 または，用いる最小の Fibonacci 数が 2, 5, 13, 34, \ldots (Fibonacci 進法で末尾の 0 が奇数個)
  • Grundy 数が 1：用いる最小の Fibonacci 数が 1 (Fibonacci 進法で末尾が 1)
  • Grundy 数が 2：用いる最小の Fibonacci 数が 3, 8, 21, 55, \ldots (Fibonacci 進法で末尾の 0 が正の偶数個)

証明

Fibonacci 数を F_0 = 0,\, F_1 = 1,\, F_i = F_{i-1} + F_{i-2} とします． g = \frac{1+\sqrt{5}}{2},\, h = \frac{1-\sqrt{5}}{2} とおいて， F_i = \frac{1}{\sqrt{5}} (g^i - h^i) です．

x \ge 1 の Zeckendorf representation の形で場合分けして x - 1 と \left\lfloor\frac{x}{g}\right\rfloor の表示を求めます．以下 F_j + \cdots の部分は番号が大きい部分の隣接しない Fibonacci 数の有限和とします (丁寧に書くと煩雑なので許してください)．

  • 偶数 i \ge 4 に対し x = F_i + F_j + \cdots のとき， x - 1 = F_3 + F_5 + \cdots + F_{i-1} + F_j + \cdots
  • 奇数 i \ge 3 に対し x = F_i + F_j + \cdots のとき， x - 1 = F_2 + F_4 + \cdots + F_{i-1} + F_j + \cdots
  • i \ge 4 に対し x = F_2 + F_i + F_j + \cdots のとき， x - 1 = F_i + F_j + \cdots

これらはすぐわかると思います ( 1 に F_3, F_5, \ldots あるいは F_2, F_4, \ldots を順に足してみてください)．

  • 偶数 i \ge 4 に対し x = F_i + F_j + \cdots のとき， \left\lfloor\frac{x}{g}\right\rfloor = F_2 + F_4 + \cdots + F_{i-2} + F_{j-1} + \cdots
  • 奇数 i \ge 3 に対し x = F_i + F_j + \cdots のとき， \left\lfloor\frac{x}{g}\right\rfloor = F_{i-1} + F_{j-1} + \cdots
  • i \ge 4 に対し x = F_2 + F_i + F_j + \cdots のとき， \left\lfloor\frac{x}{g}\right\rfloor = F_{i-1} + F_{j-1} + \cdots

これらはすぐわからないと思いますので示していきます． {} + \cdots の部分も番号が 1 ずつ小さくなります．

a = F_{i-1} + F_{j-1} + \cdots,\, b = F_i + F_j + \cdots とおくと，

\begin{align} b - g a &= \frac{1}{\sqrt{5}} ( ( (g^i - h^i) - g (g^{i-1} - h^{i-1}) ) + ( (g^j - h^j) - g (g^{j-1} - h^{j-1}) ) + \cdots) \\ &= \frac{1}{\sqrt{5}} ( ( h^{i-1} (g - h) ) + ( h^{j-1} (g - h) ) + \cdots) \\ &= h^{i-1} + h^{j-1} + \cdots \end{align}

となります． -1 \lt h \lt 0 なので，気持ちとしては， h の累乗は符号を変えながら指数的に減っていくので，一番小さい番号の部分に支配されその偶奇で符号が決まります．

i \ge 4 が偶数のとき，

\begin{align} h^{i-1} + h^{j-1} + \cdots &\gt h^{i-1} +\sum_{k=0}^\infty h^{i+2k+1} = h^{i-1} + \frac{h^{i+1}}{1 - h^2} = -h^{i-2} \ge -h^2, \\ h^{i-1} + h^{j-1} + \cdots &\lt h^{i-1} +\sum_{k=0}^\infty h^{i+2k+2} = h^{i-1} + \frac{h^{i+2}}{1 - h^2} = -h^i \lt 0 \end{align}

より -h^2 \lt b - g a \lt 0 です．これより， a - 1 \lt a - \frac{h^2}{g} \lt \frac{b}{g} \lt a および a \lt a + \frac{1-h^2}{g} \lt \frac{b+1}{g} \lt a + \frac{1}{g} \lt a + 1 が従い， \left\lfloor\frac{b}{g}\right\rfloor = a - 1,\, \left\lfloor\frac{b+1}{g}\right\rfloor = a が得られました．

i \ge 3 が奇数のとき，

\begin{align} h^{i-1} + h^{j-1} + \cdots &\gt h^{i-1} +\sum_{k=0}^\infty h^{i+2k+2} = h^{i-1} + \frac{h^{i+2}}{1 - h^2} = -h^i \gt 0, \\ h^{i-1} + h^{j-1} + \cdots &\lt h^{i-1} +\sum_{k=0}^\infty h^{i+2k+1} = h^{i-1} + \frac{h^{i+1}}{1 - h^2} = -h^{i-2} \lt -h \end{align}

より 0 \lt b - g a \lt -h です．これより， a \lt \frac{b}{g} \lt \frac{b+1}{g} \lt a + \frac{1-h}{g} = a + 1 が従い， \left\lfloor\frac{b}{g}\right\rfloor = a,\, \left\lfloor\frac{b+1}{g}\right\rfloor = a が得られました．

以上で \left\lfloor\frac{x}{g}\right\rfloor の表示は証明できました．これを用いると，元の問題の Grundy 数についての主張は帰納法で示されます．

統計情報

正解者：チーム korotkevin (0:19:32) はじめ 47 チーム

コメント

簡単な設定で黄金比が登場する Wythoff's game というゲームがよく知られています．ではゲームに黄金比を直接登場させてみるとどうなるか？という動機で問題を作ってみました．Fibonacci 進法で書いてみたらちょうどよい複雑さになっていてびっくりでした．Wythoff's game や OEIS 解に登場している Beatty sequence や Wythoff sequence といった，非負整数全体の分割が無理数や floor によって綺麗に表されるという構造が，組合せゲームとの相性がよいようですね．

おまけ

問題が \left\lfloor\frac{\sqrt{5}-1}{2} x\right\rfloor の代わりに \left\lfloor\frac{1}{2} x\right\rfloor だったらどうなるでしょう？