OMC114(E)

　うまい方法が思い付かなくても計算力次第で何とかなることもあるよということで，計算力を使って解く方法を紹介します．

　まず，$\dbinom{n}{k}$ で，$0\leq k\leq n$ のときは通常の二項係数，$k\lt0$ や $k\gt n$ のときは $0$ を表すとします．$n$ が負の場合はここでは扱いません．
　多項式 $f(x)$ の $x^n$ の係数を $[x^n]f(x)$ で表します（多項式でなくてもいいのですがここでは多項式としておきます）．例えば，$f(x)=5x^2-14x+3$ のときは， $[x^0]f(x)=3,\ [x^1]f(x)=-14,\ [x^3]f(x)=0$ などとなります．
　この記法を用いると，多項式 $f(x),g(x)$ に対し， $$\displaystyle\sum_{k=0}^n[x^k]f(x)[x^{n-k}]g(x)=[x^n] (f(x)g(x))$$ となります（証明は割愛するので各自確かめてください）．
　また，$[x^k] (1+x)^p=\dbinom{p}{k}$ であることを使うと
$$\begin{aligned} \sum_{k=0}^n\binom{p}{k}\binom{q}{n-k} &=\sum_{k=0}^n[x^k] (1+x)^p[x^{n-k}] (1+x)^q\\ &=[x^{n+k}] (1+x)^{p+q} =\binom{p+q}{n} \end{aligned}$$ となります（$k\gt p$ でも $[x^k] (1+x)^p=\dbinom{p}{k}$ は成り立っていることに注意！）．
　これは Vandermondeの恒等式 と呼ばれており，あとで使います．

　問題の解説に入ります．解説の都合上，棒を並び替えるという状況を，各マスに整数を書き込むという状況に置き換えます．スコアの期待値は，各マスでの $LlRr$ の期待値の合計になります．左から $k+1$ 番目のマスに $m+1$ が書き込まれているとして，他の $99$ マスへの整数の書き込み方 $99!$ 通りについての $LlRr$ の期待値を $E(k,m)$ とします．
　$1$ から $100$ までに $m+1$ より小さい整数は $m$ 個あり，大きい整数は $99-m$ 個あります．また， $m+1$ の左には $k$ マスあり，右には $99-k$ マスあります．
　$m+1$ より小さい $m$ 個の整数のうち $l$ 個が $m+1$ より左，$m-l$ 個が右にあるとします．このとき， $LlRr$ の値は $l(k-l)(m-l)(99-k-m+l)$ となり，このような書き込み方は $\dbinom{m}{l}\dbinom{99- m}{k-l}k!(99-k)!$ 通りあります（$l\gt k$ のときは $LlRr$ の値が負になりますが，二項係数の部分が $0$ になるので帳尻は合っています）．

　これにより， $$\begin{aligned} \displaystyle E(k,m) &=\frac{1}{99!}\sum_{l=0}^m\dbinom{m}{l}\dbinom{99- m}{k-l}k!(99-k)!\ l(k-l)(m-l)(99-k-m+l) \\ &=\frac{k!(99-k)!}{99!}\sum_{l=0}^m\frac{m!}{l!(m-l)!}\frac{(99-m)!}{(k-l)!(99-k-m+l)!}l(k-l)(m-l)(99-k-m+l) \\ &=m(m-1)(99-m)(98-m)\frac{k!(99-k)!}{99!}\sum_{l=1}^{m-1}\frac{(m-2)!}{(l-1)!(m-l-1)!}\frac{(97-m)!}{(k-l-1)!(98-k-m+l)!} \\ &=m(m-1)(99-m)(98-m)\frac{k!(99-k)!}{99!}\sum_{l=1}^{m-1}\binom{m-2}{l-1}\binom{97-m}{k-l-1} \\ &=m(m-1)(99-m)(98-m)\frac{k!(99-k)!}{99!}\binom{95}{k-2} \\ &=\frac{m(m-1)(99-m)(98-m)k(k-1)(99-k)(98-k)}{99\cdot98\cdot97\cdot96} \end{aligned}$$ と計算できます．
　求める期待値 $E$ は $$\begin{aligned} E &=\sum_{k=0}^{99}\frac{1}{100}\sum_{m=0}^{99}E(k,m)\\ &=\frac{1}{100\cdot99\cdot98\cdot97\cdot96}\left(\sum_{k=0}^{99}k(k-1)(99-k)(98-k)\right)^2 \end{aligned}$$ となります．

　次に，$S_n=\displaystyle\sum_{k=0}^nk(k-1)(n-k)(n-k-1)$ を求めましょう．$S_n$ を計算してみると， $$S_0=S_1=S_2=S_3=0,\quad S_4=4,\quad S_5=24,\quad S_6=84,\quad S_7=224,\quad S_8=504,\ldots$$ となるので， $$S_n=\dfrac{(n+1)n(n-1)(n-2)(n-3)}{30}$$ と予想できます（予想のコツは階差ではなく比を見ることです）．
　ここで，$S_n$ は高々 $5$ 次の多項式であることがわかっているので，この予想は正しいです．
　また，次のように求めることもできます．$|x|\lt1$ のとき $\displaystyle\frac{1}{1-x}=\sum_{n=0}^\infty x^n$ であることを思い出しましょう．すると，$\displaystyle[x^n]\frac{1}{1-x}=1$ と書けます（$[x^n]f(x)$ の説明で多項式でなくてもよいと言っていましたが，これのことです．収束半径内であれば項の順序を変えてもよいので，畳み込みの式も成り立っています）．微分することで $$\displaystyle[x^n]\frac{2}{(1-x)^3}=(n+1)(n+2),\quad [x^n]\frac{120}{(1-x)^6}=(n+1)(n+2)(n+3)(n+4)(n+5)$$ を得ます（級数と微分は入れ替えてよいときと悪いときがありますが，今回はよいときです）．
　これを使うと， $$\begin{aligned} S_n &=\sum_{k=0}^n[x^{k-2}]\frac{2}{(1-x)^3}[x^{n-k-2}]\frac{2}{(1-x)^3}\\ &=[x^{n-4}]\frac{4}{(1-x)^6}=\dfrac{(n+1)n(n-1)(n-2)(n-3)}{30} \end{aligned}$$ と計算できます．

　最後に，$S_n=\dfrac{(n+1)n(n-1)(n-2)(n-3)}{30}$ を代入すると， $$\begin{aligned} E&=\frac{S_{99}^2}{100\cdot99\cdot98\cdot97\cdot96} &=\frac{100\cdot99\cdot98\cdot97\cdot96}{900}=\mathbf{10038336} \end{aligned}$$ となります．

　解説なので長くなりましたが，これぐらいの計算なら慣れれば10分ほどで終わります．