writer/testerのみなさんありがとうございました。

Eまではサクッと解けた気がします。（WAを山のように出してしまった、ひえぇ）

F・Gやばすぎる…

Fの解説が気になる。こんなの解けるんですね。

A No.1033 乱数サイ

$K$ 個のサイコロを振ると考えればよいんですかね？サンプルを見ながら式変形してたら $N/2$ になってびっくりしました。期待値なのでそれはそうかも。

B No.1034 テスターのふっぴーさん

この問題、コンテスト中じゃなくて普段の精進で出会いたかったですね。

解き方は分かっても実装の前にだいぶ慎重になりました。良問な気がする。

4つの壁までの距離を出しておいて、タマネギの皮を外すみたいに外側から削っておき、壁沿いに $(I, J)$ があるような状態に帰着させて解きました。

C No.1035 Color Box

包除原理

「 $M$ 種類以下」のペンキで塗り分ける方法を各 $M$ について求めて足したり引いたりします。

D No.1036 Make One With GCD 2

連続部分列という問題設定、またある連続部分列が条件を満たしたらそれを左右に延長したものも条件を満たすことから、尺取り法ができそう。

しかし、ある区間でgcd=1として、左端をひとつ右にずらしたらgcdがどうなるかというのは $O(1)$ では計算できない。

セグ木ぺたり（ええ）

これで $l$ を1ずつforループで動かしながら $r$ を適宜右にずらすと答えが出ます。計算量 $O(n \log n \log a)$

gcdの単位元は $0$ でしたね（毎回ちょっとだけ不安になる）

追記：sliding window aggregationなるものを使うとlogが落とせる。

E No.1037 exhausted

パッと見て最初に浮かぶのは蟻本P73のExpedition（めっちゃ似てる）なんですが、 $w_i$ の処理をどうしたものかとしばらくストールしてしまいました。

各地点での最適な状況はその地点にいるときにはまだわからないけど、 $(地点, 残り燃料)$ について最適化して遷移していけば良さそうなので、DP。実際 $O(NV)$ が入りきります。

$\mathrm{DP}(i, j) = x_i$ 地点で残り燃料が $j$ のときの最小費用

$x_0 = 0, x_{n+1} = L$ とすると楽でした。

DEGwerさんの数え上げテクニック集の[14.1 頻出公式集]を形式的べき級数などを用いて証明します。

上の参照先にある通り組合せ論的な解釈で片付くものも多いですが、あえて代数的な証明を目指します。

あまりちゃんとした（？）勉強の仕方をしておらず、厳密な正しさに欠けるところも多いと思います。間違っているところや不適切な表現があればご指摘いただけると幸いです。

1~4は割と基本的なので適宜飛ばし読みしてください。

前提知識

ここで、いくつかこの記事で利用する式変形などを確認します。形式的べき級数の定義や基本的な演算についてはこの記事の範囲外とします。

（記法） $[x^{t}] F$

形式的べき級数 $F$ を $\sum_i c_i x^{i}$ と表した時の $x^{t}$ の係数をこのように表します。

$\displaystyle \frac{1}{1-x} = 1 + x + x^{2} + \cdots$

等比数列の和の公式と思ってもよいと思います。

$\displaystyle \sum_{i=0}^{k} [x^{i}]F = [x^{k}] \frac{1}{1-x}F$

形式的べき級数 $F$ の係数の部分和です。 $\frac{1}{1-x} = 1 + x + x^{2} + \cdots$ となることを考えれば自然かと。

（定義） ${n \choose k} = \frac{n(n-1)\cdots(n-k+1)}{k!}$ （ $k$ は非負整数）

二項係数です。 ${}_n\mathrm{C}_k$ とも書かれます。

$\displaystyle (1+x)^{n} = \sum_{k=0}^{\infty} {n \choose k} x^{k}$

二項定理。和の取る範囲が普通のものと違っていますが、 $n > k$ のとき ${n \choose k} = 0$ なのでよく知られているものと同じといえます。自然数 $n$ に対しては、帰納法や組合せの解釈で証明できます。

$\displaystyle \frac{1}{(1-x)^{n+1}} = \sum_{k=0}^{\infty} {n+k \choose k} x^{k}$

二項定理のマイナスバージョン。ここらへんの式たちは、テイラー展開の操作も考えてみると面白いかもしれません。

（小ネタ）ここまでで気が付いたかもしれませんが、これらの定理は $n$ を任意の複素数に拡張することができます。先ほどのマイナスバージョンも二項定理の $n$ を置き換えると出てきます。証明は大変ですが調べてみてください。詳細はWikipedia

ここから実際の内容に入っていきます。

1/6

◇ $\displaystyle \sum_{i=0}^{\infty} {n \choose i} = 2^{n}$

これは二項定理より明らかです。先ほどの式に $x=1$ を代入するだけですね。

2/6

◇ $\displaystyle \sum_{i=0}^{\infty} {n \choose 2i} = 2^{n-1}$

$i$ が奇数の場合が打ち消されてほしいので、上の二項定理の式で $x$ を $-x$ に置換し、下の式を得ます。

$\displaystyle (1-x)^{n} = \sum_{k=0}^{\infty} {n \choose k} (-1)^{k}x^{k}$

これをもとの $(1+x)^{n}$ の式と足し合わせて $x = 1$ を代入し $2$ で割るとこの等式を得ることができます。

二項係数の漸化式を利用する方法もありますね。そちらの方が簡単かもしれません。

ここまでが普通の関数としての処理になります。

3/6

◇ $\displaystyle \sum_{i=0}^{k} {n+i \choose i} = {n+k+1 \choose k}$

二項定理のマイナスバージョンを使ってほしそうな顔をしています。

$\displaystyle \sum_{i=0}^{\infty} {n+i \choose i} x^{i} = \frac{1}{(1-x)^{n+1}}$

これの係数の部分和をとるだけです。最初の方に挙げた公式を使います。

$\displaystyle \sum_{i=0}^{k} {n+i \choose i} = [x^{k}] \frac{1}{1-x}\frac{1}{(1-x)^{n+1}} = [x^{k}] \frac{1}{(1-x)^{n+2}}$

ここでついさっき使ったばかりの二項定理をもう一度逆に使うと、欲しい式が現れます。

$\displaystyle [x^{k}] \frac{1}{(1-x)^{n+2}} = {n+k+1 \choose k}$

行って帰ってきたらちょっと違う顔をしてた、みたいな感じでおもしろい。

一応この等式はパスカルの三角形での和を考えると直感的です。

4/6

◇ $\displaystyle \sum_{i=0}^{k} \sum_{j=0}^{l} {i+j \choose i} = {k+l+2 \choose k+1} - 1$

（出典と少し違いますが、こちらの式が正しいはずです）

先ほどのものとほとんど同じですね。3/6の式をシグマの数だけ適用します。 ${n \choose k} = {n \choose n-k}$ もサラっと2回使っています。

$\displaystyle \sum_{i=0}^{k} \sum_{j=0}^{l} {i+j \choose i} = \sum_{i=0}^{k} {i+l+1 \choose l} = \sum_{i=1}^{k+1} {i+l \choose i} = {k+l+2 \choose k+1} - {l \choose 0}$

たどり着けました。

先ほど同様、パスカルの三角形で長方形の部分の和をとると言い換えられ、3.の手順を2重に繰り返せばイメージが付きます。

ここまでは単に公式を当てはめることで和の計算ができ、イメージも容易でした。

次から式が複雑になり、解釈が難しくなってきます。

5/6

◇ $\displaystyle \sum_{i=0}^{k} {n \choose i} {m \choose k-i} = {n+m \choose k}$

二項係数同士の積が出てきました。一筋縄ではいかなそうに見えます。

このような形の式はしばしば、以下のようなで手順で計算できるようです。

シグマの中身を変数をひとつ選んで（ここでは $n$ とする） $f(n)$ と表す。ここは経験（と試行錯誤）が必要？
$f(n)$ を係数に持つ形式的べき級数 $F=\sum_{i=0}^{\infty} f(n)x^{n}$ をおく。
シグマの順序を入れ換え、式をくくりだすなどして簡単な形にもっていく。
$F=\sum_{i=0}^{\infty} c_i x^{i}$ の形にバラす。

この通りにやってみます。

選ぶ変数として $k,\,n,\,m$ が考えられます。ここでは $i$ の動く範囲が中途半端で扱いづらいので $k$ にします。
$\displaystyle F = \sum _ {k=0}^{\infty} \sum _ {i=0}^{k} {n \choose i}{m \choose k-i} x^{k}$ とおきます。
$\displaystyle F = \sum _ {i=0}^{\infty} {n \choose i} \sum _ {k=i}^{\infty} {m \choose k-i} x^{k} = \sum _ {i=0}^{\infty} {n \choose i} (1+x)^{m}x^{i} = (1+x)^{m}(1+x)^{n}$
$F=(1+x)^{m+n}$ より $\displaystyle [x^{k}]F = {n+m \choose k}$

できました！

これはVandermondeの恒等式と呼ばれるものらしいです。最終的には $(1+x)^{n}(1+x)^{m} = (1+x)^{n+m}$ の係数を比較しているだけだということもわかりました。

6/6

◇ $\displaystyle \sum _ {i=0}^{k} {n+i \choose i}{m-i \choose k-i} = {n+m+1 \choose k}$

同じです。

$k$ を選びます。
$\displaystyle F = \sum _ {k=0}^{\infty} \sum _ {i=0}^{k} {n+i \choose i}{m-i \choose k-i} x^{k}$ とおきます。
$\displaystyle {F = \sum _ {i=0}^{\infty} {n+i \choose i} \sum _ {k=i}^{\infty} {m-i \choose k-i} x^{k} = \sum _ {i=0}^{\infty} {n+i \choose i} (1+x)^{m-i}x^{i} \\ = (1+x)^{m} \sum _ {i=0}^{\infty} {n+i \choose i} \frac{x^{i}}{(1+x)^{i}} = (1+x)^{m} \frac{1}{\left(1-\frac{x}{1+x}\right)^{n+1}} = (1+x)^{m}(1+x)^{n+1}}$
$F=(1+x)^{m+n+1}$ より $\displaystyle [x^{k}]F = {n+m+1 \choose k}$