　一般に棒の本数を $N \geq 5$ として考える．並べられた $N$ 本のうち $5$ 本の棒の組み合わせを単に**組**と呼び，組の中で左から $3$ 番目の棒をその組の**中心**と呼び，組であって以下を満たすものを**良い組**と呼ぶことにする．
- 組を構成する棒のうち中心より長いものが，中心の左右にちょうど $1$ 本ずつ存在する．

　$1$ 本の棒 $s$ に着目したとき，$s$ に割り当てられる数は $s$ を中心とする良い組の個数に等しい．したがって棒の並べ方における良い組すべての個数が，その棒の並べ方のスコアに一致する．\
　ここで $N$ 本のうち $5$ 本の組み合わせを固定すると，これが良い組となる確率は $16\/5!=2\/15$ であることがわかる．したがって，求める期待値は $2{}\_{N}\mathrm{C}\_{5}\/15$ であり， $N=100$ でこれは $\mathbf{10038336}$ である．
公式解説
https://onlinemathcontest.com/contests/omc114/editorial/5248
　うまい方法が思い付かなくても計算力次第で何とかなることもあるよということで，計算力を使って解く方法を紹介します．

----

　まず，$\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分ほどで終わります．
ユーザー解説
https://onlinemathcontest.com/contests/omc114/editorial/5248/115
tria_math_ さんの解説に関連して，ラグランジュ補間を用いた解法について説明します．ラグランジュ補間については多くの文献がインターネットにもあるので，そちらも適宜参照してください．今回の解説は高校数学の美しい物語さんの記事 (https:\/\/manabitimes.jp\/math\/726) さえ読めば十分理解できると思います．

それでは本問の解説に移ります．

---


tria_math_ さんの解説で $S_n$ を求めるのに予想を用いていましたが，ここでは予想を使わずに $S_n$ を求める方法を書きます．以下，$S_n$ は $n$ に対する高々 $5$ 次の多項式として見たほうが都合が良いので，$S(n)$ と表記することとします．

$S(0),S(1),\ldots,S(5)$ を求めると，$S(0)=S(1)=S(2)=S(3)=0,S(4)=4,S(5)=24$ です．ラグランジュ補間を用いると気合で $S(99)$ が計算できます．

$\displaystyle f_k(x)=\frac{\prod_{i=0}^5 (x-i)}{x-k}$ と置きます．ラグランジュの補間公式より

$$\begin{aligned}
S(99) &=  \sum_{i=0}^5 S(i)\frac{f_i(99)}{f_i(i)} \\\\
&=4\frac{f_4(99)}{f_4(4)} + 24\frac{f_5(99)}{f_5(5)}\\\\
& =99\times98\times97\times96\times95\times94 \times  \Big( -\frac{4}{95\times 24} + \frac{24}{94\times 120} \Big)\\\\
& = 99\times98\times97\times96\times   \Big( -\frac{4\times 94}{ 24} + \frac{95 \times 24}{ 120} \Big)\\\\
&= 99\times98\times97\times96\times\frac{10}{3}
\end{aligned}$$

が得られます．以下 tria_math_ さんの解説に合流します．

---

ラグランジュ補間は競技数学界隈ではあまりメジャーではない気がしますが，本問のように便利に使えることもあります．（計算が大変なときもあります．） 是非テクニックの一つとして覚えていただけると嬉しいです．

---

ラグランジュ補間の練習問題です．

OMC081-F (https:\/\/onlinemathcontest.com\/contests\/omc081\/tasks\/2518)
ユーザー解説
https://onlinemathcontest.com/contests/omc114/editorial/5248/116
　長さの相異なる $100$ 本の棒があります．これらを左右一列に並べ，それぞれの棒に対して以下のように非負整数を割り当てます．
- 自身より長い棒の中で，自身より左・右にあるものの個数をそれぞれ $L, R$ とする．また，自身より短い棒の中で，自身より左・右にあるものの個数をそれぞれ $l, r$ とする．このときの $LRlr$ の値を割り当てる．

すべての棒に割り当てた数の総和を，棒の並べ方に対する**スコア**とします．\
　$100!$ 通りの棒の並べ方すべてに対して，スコアの平均を求めて下さい．