ABC 405 E についての雑談

apple, banana, cherry, durian とかにしてほしかった...

atcoder.jp

• 考察
  • 立式
  • 計算量改善
  • おまけ
  • おまけのおまけ
• あとがき
• おわり

考察

コンテスト中にやった考察に沿って話を進めます。

立式

一番右の A と一番右の B に注目します。それらの間に C が含まれるケースは次のようになります。

AAAABBBABBA ++ A ++ BCCBB ++ B ++ CDCCCCDCDD

すなわち、次を連結したものになります。

• $A-1$ 個の A と、$i$ ($0\le i\lt B$) 個の B を任意の順に並べたもの
• $1$ 個の A
• $B-i-1$ 個の B と、$j$ ($1\le j\le C$) 個の C を任意の順に並べたもの
• $1$ 個の B
• $C-j$ 個の C と $D$ 個の D を任意の順に並べたもの

よって、この通り数は次の式で表せます。 $$ \begin{aligned} &\phantom{{}={}} \sum_{i=0}^{B-1} \sum_{j=1}^C \binom{A-1+i}{i} \binom{B-i-1+j}{j} \binom{C-j+D}{D} \\ &= \sum_{i=0}^{B-1} \binom{A-1+i}{i} \sum_{j=1}^C \binom{B-i-1+j}{j} \binom{C-j+D}{D} \end{aligned} $$

また、それらの間に C が含まれないケースは次のようになります。

AABABBAABAABABBA ++ CDDCDCDCCCCDCC

すなわち、次を連結したものになります。

• $A$ 個の A と、$B$ 個の B を任意の順に並べたもの
• $C$ 個の C と、$D$ 個の D を任意の順に並べたもの

特に、A と C の制約から、一番右の B よりも一番右の A の方が右に来るケースもこちらに含まれます。 この通り数は次のようになります。

$$ \binom{A+B}{B} \binom{C+D}{D} $$

計算量改善

後者のケースはいいとして、前者のケースの内側の $\sum$ を高速に計算する必要があります。 $$ \sum_{i=0}^{B-1} \binom{A-1+i}{i} \underbrace{\sum_{j=1}^C \binom{B-i-1+j}{j} \binom{C-j+D}{D}}_{b_i} $$ すなわち、この $b_i$ の部分です。とりあえず Wolfram|Alpha に投げます。 $$ b_i = \frac{C+D}C\binom{C+D-1}{D} \cdot({}_2 F_1(-C, B-i; -C-D; 1)-1) $$ 二項係数と階乗の部分を整理すると下記になります。 $$ b_i = \frac{(C+D)!}{D!\,C!} \cdot({}_2 F_1(-C, B-i; -C-D; 1)-1) $$

ここで、${}_2 F_1(a, b; c; z)$ は 超幾何関数 (hypergeometric function) と呼ばれ、下記で与えられるらしいです*1。 $$ {}_2 F_1(a, b; c; z) = \sum_{n=0}^{\infty} \frac{(a)_n\,(b)_n}{(c)_n}\cdot\frac{z^n}{n!} $$ $(a)_n$ は Pochhammer の上昇階乗冪で、$(a)_n = a\cdot(a+1)\cdot\cdots\cdot(a+n-1)$ です。Wolfram|Alpha では Hypergeometric2F1 という名前で定義されています。

困っているようす

$c\lt a\lt 0\le b$ として、 $$ \begin{aligned} {}_2 F_1(a, b; c; 1) &= \sum_{n=0}^{\infty} \frac{(a)_n\,(b)_n}{(c)_n}\cdot\frac{1}{n!} \\ &= \sum_{n=0}^{|a|} \frac{(a)_n\,(b)_n}{(c)_n}\cdot\frac{1}{n!} \\ &= \sum_{n=0}^{|a|} \frac{(a)_n}{(c)_n}\cdot\frac{(b)_n}{n!} \\ &= \sum_{n=0}^{|a|} \frac{a\cdot(a+1)\cdot\cdots\cdot(a+n-1)}{c\cdot(c+1)\cdot\cdots\cdot(c+n-1)}\cdot\frac{(b)_n}{n!} \\ &= \sum_{n=0}^{|a|} \frac{|a|\cdot(|a|-1)\cdot\cdots\cdot(|a|-(n-1) )}{|c|\cdot(|c|+1)\cdot\cdots\cdot(|c|-(n-1) )}\cdot\frac{(b)_n}{n!} \\ &= \sum_{n=0}^{|a|} \frac{|a|!}{(|a|-n)!} \frac{(b+n-1)!}{(b-1)!} \frac{(|c|-n)!}{|c|!} \frac1{n!} \\ &= \sum_{n=0}^{|a|} \frac{|a|!}{(|a|-n)!\,n!} \frac{(b+n-1)!}{(b-1)!\,n!} \frac{(|c|-n)!\,n!}{|c|!} \\ &= \sum_{n=0}^{|a|} \binom{|a|}{n} \binom{b+n-1}{n} \binom{|c|}{n}^{-1} \end{aligned} $$ ここからどうすれば...？ リンク先の式 (74) によれば $$ {}_2 F_1(a, b; c; 1) = \frac{\Gamma(c)\,\Gamma(c-a-b)}{\Gamma(c-a)\,\Gamma(c-b)} $$ らしいです。ここでは $c$ が負なのでハチャメチャに発散しそうです。困った。

$a\lt 0$ や $\Gamma(n) = (n-1)\,\Gamma(n-1)$ などから $$ \begin{aligned} {}_2 F_1(a, b; c; 1) &= \frac{\Gamma(c)\,\Gamma(c-a-b)}{\Gamma(c-a)\,\Gamma(c-b)} \\ &= \frac{\Gamma(c)}{\Gamma(c-a)}\frac{\Gamma(c-a-b)}{\Gamma(c-b)} \\ &= \frac{\Gamma(c)}{(c-a-1)\,\Gamma(c-a-1)}\frac{(c-a-b-1)\,\Gamma(c-a-b-1)}{\Gamma(c-b)} \\ &= \cdots \\ &= \frac{(c-a-b-1)\cdot\cdots\cdot(c-b)}{(c-a-1)\cdot\cdots\cdot c} \end{aligned} $$ としてよいのであれば、計算はできそうです。今回計算したいのは ${}_2 F_1(-C, B-i; -C-D; 1)$ だったので、 $$ \begin{aligned} &\phantom{{}={}} {}_2 F_1(-C, B-i; -C-D; 1) \\ &= \frac{-C-D-(-C)-(B-i)-1}{-C-D-(-C)-1}\cdot\cdots\cdot\frac{-C-D-(B-i)}{-C-D} \\ &= \frac{-D-B+i-1}{-D-1}\cdot\cdots\cdot\frac{-C-D-B+i}{-C-D} \\ &= \frac{(B-i)+(D+1)}{D+1}\cdot\cdots\cdot\frac{(B-i)+(D+C)}{D+C} \\ &= \frac{( (B-i)+(D+C) )!}{( (B-i)+D)!}\cdot\frac{D!}{(D+C)!} \end{aligned} $$ となりそうです。

たとえば、$(B, C, D, i) = (10, 5, 2, 3)$ としてみると、${}_2 F_1(-5, 7; -7; 1) = \frac{286}3$ となり*2、 $$ \begin{aligned} b_i &= \frac{7!}{2!\,5!}\cdot({}_2 F_1(-5, 7; -7; 1)-1) \\ &= 21\cdot \left(\frac{286}3-1\right) \\ &= 7\cdot(286-3) \\ &= 1981 \end{aligned} $$ となり、元々の $\sum$ で計算した値と一致します。$\eod$

コンテスト本番では、超幾何関数はどうしようもないと思っていたので別の方針を考えました。 $B$, $C$, $D$ を $1$ ずつ変えながら値を眺めることで、下記に気づきます。

Observation 1: $b_B = 0$ かつ、各 $0\le i\lt B$ に対して下記が成り立つ。 $$ b_i = b_{i+1} + \binom{(B-1)-i+C+D}{C-1} $$

$(B-1)-i$ の部分や漸化式の向きなどから、$b'_i$ を下記で定義します。 $$ b'_i = \sum_{j=1}^C \binom{i+j}{i} \binom{C-j+D}{D} $$ なお、$b'_i = b_{(B-1)-i}$ です。

Conjecture 2: $b_{-1} = 0$ かつ、各 $0\le i\le B-1$ に対して下記が成り立つ。 $$ b'_i = b'_{i-1} + \binom{i+C+D}{C-1} $$

More observations

$i=0$ のとき、Hockey-stick identity から $$ \begin{aligned} b'_0 &= \sum_{j=1}^C \binom jj\binom{C-j+D}D \\ &= \sum_{j=1}^C \binom{C-j+D}D \\ &= \sum_{j'=0}^{C-1} \binom{D+j'}D \\ &= \binom{D+C}{D+1} \end{aligned} $$ が成り立つ。一方、 $$ \begin{aligned} b'_0 &= b'_{-1} + \binom{C+D}{C-1} \\ &= 0 + \binom{D+C}{D+1} \end{aligned} $$ より、$i = 0$ のときは成り立つ。

$$ \begin{aligned} b'_i - b'_{i-1} &= \sum_{j=1}^C \binom{i+j}j\binom{C-j+D}D - \sum_{j=1}^C \binom{i-1+j}j\binom{C-j+D}D \\ &= \sum_{j=1}^C \left( \binom{i+j}j - \binom{i-1+j}j\right) \binom{C-j+D}D \\ % &= \sum_{j=1}^C \left( \frac{(i+j)!}{i!\, j!} - \frac{(i+j-1)!}{(i-1)!\, j!}\right) \binom{C-j+D}D \\ % &= \sum_{j=1}^C \left( \frac{(i+j)!}{i!\, j!} - \frac{i}{i+j}\frac{(i+j)!}{i!\, j!}\right) \binom{C-j+D}D \\ % &= \sum_{j=1}^C \frac{j}{i+j}\frac{(i+j)!}{i!\, j!} \binom{C-j+D}D \\ % &= \sum_{j=1}^C \frac{(i+j-1)!}{i!\, (j-1)!} \binom{C-j+D}D \\ &= \sum_{j=1}^C \binom{i-1+j}{j-1} \binom{C-j+D}D \\ &= \sum_{j=0}^{C-1} \binom{i+j}{j} \binom{C-1-j+D}D \\ &= \sum_{j=0}^{C-1} \binom{i+j}{i} \binom{C-1-j+D}D \\ % &= \sum_{j=0}^{C-1} \binom{i+j}{i} \binom{C-1-j+D}D \\ % &= \binom{i+C+D}{i+D+1} \\ % &= \binom{i+C+D}{C-1}. \quad\qed \end{aligned} $$

よって、下記が成り立てばよい。 $$ \sum_{j=0}^{C-1} \binom{i+j}{i} \binom{C-1-j+D}D = \binom{i+D+C}{i+D+1}. $$

Lemma 3: 下記が成り立つ。

$$ \sum_{i=0}^{k-1} \binom{n+i}{n} \binom{m+k-1-i}{m} = \binom{n+m+k}{n+m+1}. $$

note: Pascal の三角形の $n$ 列目と $m$ 列目から $k$ 個持ってきたものの畳み込みに相当する。

                           .  
                         .   .  
                       .   .   A  
                     .   .   B   .  
                   .   .   C   .   .  
                 .   .   D   .   .   .  
               .   .   E   .   .   .   e  
             .   .   .   .   .   .   d   .  
           .   .   .   .   .   .   c   .   .  
         .   .   .   .   .   .   b   .   .   .  
       .   .   .   .   .   .   a   .   .   .   .  
     .   .   .   .   .   .   .   .   .   .   .   .  
   .   .   .   .   .   .   .   .   .   .   .   .   .  
 .   .   .   .   .   .   .   .   .  [*]  .   .   .   .  

Proof

$m$, $k$ に関する帰納法で示す。

$$ P(m, k) \iff \ForallL{n}{\sum_{i=0}^{k-1} \binom{n+i}{n} \binom{m+k-1-i}{m} = \binom{n+m+k}{n+m+1}} $$ とする。

To-be-proved 1: $P(m, 1)$

$$ \begin{aligned} \sum_{i=0}^{1-1} \binom{n+i}{n} \binom{m+1-1-i}{m} &= \binom{n}{n} \binom{m}{m} \\ &= 1, \\ \binom{n+m+1}{n+m+1} &= 1. \end{aligned} $$

To-be-proved 2: $P(m, k+1) \wedge P(m+1, k) \implies P(m+1, k+1)$

$$ \begin{aligned} &\phantom{{}={}} \sum_{i=0}^{(k+1)-1} \binom{n+i}{n} \binom{(m+1)+(k+1)-1-i}{m+1} \\ &= \sum_{i=0}^{(k+1)-1} \binom{n+i}{n} \left(\binom{(m+1)+(k+1)-1-i-1}{(m+1)-1} \right. \\ & \qquad\qquad\qquad\qquad\quad {} + \left. \binom{(m+1)+(k+1)-1-i-1}{m+1}\right) \\ &= \sum_{i=0}^{(k+1)-1} \binom{n+i}{n} \binom{(m+1)+(k+1)-1-i-1}{(m+1)-1} \\ &\qquad\qquad {} + \sum_{i=0}^{k-1} \binom{n+i}{n} \binom{(m+1)+(k+1)-1-i-1}{m+1} \\ &\qquad\qquad {} + \binom{n+k}{n} \binom{(m+1)+(k+1)-1-k-1}{m+1} \\ &= \sum_{i=0}^{(k+1)-1} \binom{n+i}{n} \binom{m+(k+1)-1-i}{m} + \sum_{i=0}^{k-1} \binom{n+i}{n} \binom{(m+1)+k-1-i}{m+1} + 0 \\ &= \binom{n+m+(k+1)}{n+m+1} + \binom{n+(m+1)+k}{n+(m+1)+1} \\ &= \binom{n+(m+1)+(k+1)}{n+(m+1)+1}. \quad\qed \end{aligned} $$

なんかふつうにお出しされた。最初から教えてよ〜 www.wolframalpha.com

変数を $k$ から $d$ に変えたら出してくれなくなり、これマジ？となりました。 www.wolframalpha.com

比較のために見ておくと、Vandermonde identity は下記のような畳み込みです。うまいこと帰着できたりするのかな？

                               .  
                             .   .  
                           .   .   .  
                         .   .   .   .  
                       A   B   C   D   .  
                     .   .   .   .   .   .  
                   .   .   .   .   .   .   .  
                 d   c   b   a   .   .   .   .  
               .   .   .   .   .   .   .   .   .  
             .   .   .   .   .   .   .   .   .   .  
           .   .   .   .   .   .   .   .   .   .   .  
         .   .   .  [*]  .   .   .   .   .   .   .   .  

Corollary 4: 任意の $n\ge 1$ に対して下記が成り立つ。

$$ \sum_{i=0}^{k-1} \binom{n+i}{n} \binom{m+k-1-i}{m} = \sum_{i=0}^{k-1} \binom{n-1+i}{n-1} \binom{m+k-i}{m+1} $$

Proof: Lemma 3 より明らか。

これを示して $n = 0$ に帰着させることで Hockey-stick identity から Lemma 3 を示す方針を考えていましたが、こちらが Corollary になりました。

おまけ

ここまでの考察で、$b_i$ を incremental に求めることで $i$ ごとに定数時間で求められることがわかりました。コンテスト中はそれで十分でしたが、もう少し進めてみます。

下記が成り立ちます。 $$ \begin{aligned} b_i &= \sum_{j=1}^C \binom{B-i-1+j}{j} \binom{C-j+D}{D} \\ &= \sum_{j=1}^C \binom{B-i+j-1}{B-i-1} \binom{C-j+D}{D} \\ &= \sum_{j=0}^{C-1} \binom{B-i+j}{B-i-1} \binom{C-1-j+D}{D} \\ &= \left( \sum_{j=0}^{C} \binom{B-i-1+j}{B-i-1} \binom{C-j+D}{D} - \binom{B-i-1}{B-i-1} \binom{C+D}{D} \right) \\ &= \binom{(B-i-1)+D+(C+1)}{(B-i-1)+D+1} - \binom{C+D}{D} \\ &= \binom{B+C+D-i}{B+D-i} - \binom{C+D}{D} \\ &= \binom{B+C+D-i}{C} - \binom{C+D}{D} \\ \end{aligned} $$

よって、冒頭に挙げた前者のケースの通り数は $$ \begin{aligned} &\phantom{{}={}} \sum_{i=0}^{B-1} \binom{A-1+i}{i} \sum_{j=1}^C \binom{B-i-1+j}{j} \binom{C-j+D}{D} \\ &= \sum_{i=0}^{B-1} \binom{A-1+i}{i} \left( \binom{B+C+D-i}{C} - \binom{C+D}{D} \right) \\ &= \sum_{i=0}^{B-1} \binom{A-1+i}{A-1} \binom{B+C+D-i}{C} - \binom{C+D}{D} \sum_{i=0}^{B-1} \binom{A-1+i}{A-1} \\ &= \sum_{i=0}^{B-1} \binom{A-1+i}{A-1} \binom{B+C+D-i}{C} - \binom{A-1+B}{A} \binom{C+D}{D} \end{aligned} $$ となります。後者のケースと合わせて、全体の答えは $$ \begin{aligned} &\phantom{{}={}} \sum_{i=0}^{B-1} \binom{A-1+i}{A-1} \binom{B+C+D-i}{C} \\ &\qquad\quad {} - \binom{A-1+B}{A} \binom{C+D}{D} + \binom{A+B}{A} \binom{C+D}{D} \\ &= \sum_{i=0}^{B-1} \binom{A-1+i}{A-1} \binom{B+C+D-i}{C} + \binom{A+B-1}{A-1} \binom{C+D}{D} \\ &= \sum_{i=0}^{B} \binom{A-1+i}{A-1} \binom{B+C+D-i}{C} \end{aligned} $$ とできますね。

また、対称性から、入力が $(A, B, C, D)$ のときの答えと $(D, C, B, A)$ のときの答えが一致することもわかります。実際、 $$ \begin{aligned} &\phantom{{}={}} \sum_{i=0}^{B} \binom{A-1+i}{A-1} \binom{B+C+D-i}{C} \\ &= \sum_{i=0}^{C} \binom{D-1+i}{D-1} \binom{C+B+A-i}{B} \\ &= \sum_{i=0}^{C} \binom{D-1+C-i}{D-1} \binom{B+A+i}{B} \\ &= \sum_{i=0}^{C} \binom{A+B+i}{B} \binom{D-1+C-i}{D-1} \\ \end{aligned} $$ となり、公式解説 と同じ式が得られました。

ということで、この畳み込みも高速化できないものかね？という気持ちになります。下記が成り立つらしいです。 $$ \begin{aligned} &\phantom{{}={}} \sum_{i=0}^{k-1} \binom{n+r+i}{n} \binom{m+k-1-i}{m} \\ &= \binom{k+m-1}{m}\binom{n+r}{r} {}_3 F_2 (1, 1-k, n-r+1; -k-m+1, r+1; 1). \end{aligned} $$ なんやかんやで答えは下記になります。 $$ \begin{aligned} \binom{A+B}{A} \binom{C+D-1}{C} {}_3 F_2(1, -C, A+B+1; A+1, -C-D+1; 1) \end{aligned} $$ ${}_3 F_2$ を高速に有理数表示で計算する方法（の存在）がわからず、おわりです...

定義通りの $$ {}_p F_q(a_1, \dots, a_p; b_1, \dots, b_q; z) = \sum_{n=0}^{\infty} \frac{(a_1)_n\cdot\cdots\cdot(a_p)_n}{(b_1)_n\cdot\cdots\cdot(b_q)_n}\frac{z^n}{n!} $$ の $n$ 項目の各 factor を持っておけば、次の項は $O(p+q)$ 時間程度で計算できます。$n\ge C$ のとき $(-C)_n = 0$ なので先頭 $C$ 項だけ見ればよいことから $O(C)$ 時間で求められはしますが、なんだかな〜という感じですね。

もしかして二項係数関連のどうにもならない積和を超幾何関数として追いやっているだけですか？

おまけのおまけ

$$ \begin{aligned} {}_3 F_2 (1, 1-k, n+1; -k-m+1, 1; 1) &= {}_2 F_1 (1-k, n+1; -k-m+1; 1) \end{aligned} $$ が成り立つらしいので、$r=0$ を考えて $$ \begin{aligned} {}_2 F_1 (1-k, n+1; -k-m+1; 1) = \binom{n+m+k}{n+m+1} \binom{k+m-1}{m}^{-1} \end{aligned} $$ であり、$(k-1, n+1, m-a) = (a, b, c)$ として $$ \begin{aligned} {}_2 F_1 (-a, b; -c; 1) = \binom{b+c}{b+c-a} \binom{c}{c-a}^{-1} \end{aligned} $$ を得ます。

あとがき

たぶん失敗方針ではありそうな気もしつつ、おもしろい等式を知ることができたのでよかったな〜という感じです。 超幾何関数とも知り合いになれました。

この手の問題で、「とりあえず愚直を書いて、差分を睨んでいたら二項係数が出てくるだろうから、エスパーして合わせればなんとかなる」みたいなやり方ばかりやっているのはやっぱりよくないと思います。でも頭を使わずに済むから楽なんですよね。頭を使いたくないなら ABC をやめればいいのに... とも思いますし、ABC で頭を使っている時点で負けという気もします。

気づいたら日曜が終わろうとしているのは納得いきません。本題の浮動小数点数シリーズの方は進捗がありません。えびちゃんだって進捗を出したいと思っています。

おわり

おわりです。