ARC077 D - 11 - ツバサの備忘録

解法

ダブっている数字は数列に1つ必ず存在します。
ダブってる数字のうち左側にあるものを $x$ ,右側にあるものを $y$ としたとき、数列は次のようになっています。
$l, x, m, y, r$
ここで、 $l,m,r$ はそれぞれ0個以上の要素を持っている数列です。
長さ $k$ の部分列を数え上げる方針としては、まず
$l, x, m, r$ という $y$ を除いたパターンを数え、その後 $y$ が存在した場合に新しく作成できるパターンを計算して合算します。

$y$ を無視した場合
$l, x, m, r$
という数列には、 $1$ ～ $n$ の数字がすべて1つずつ含まれています。ので、全ての数字について、使うか使わないかの2通りを考えればよく、これは
$_nC_k$
となります。
$y$ を考慮した場合
新しく増えるパターンは、必ず $y$ を使用します。なぜなら、使用しないパターンはすでに前の段階で数えているからです。
ここは、さらに2つに場合分けします。 $x$ を部分列に含むか含まないか、です。

$x$ を含む場合
$x,y$ を使用することが確定しているので、残った $l,m,r$ の部分から $k-2$ 個を選びます。ということで
$_{(n-1)}C_{(k-2)}$
となります。
$x$ を含まない場合
$x$ と $y$ が同じ数字であるので、被りがないように数え上げなければなりません。
ここで、どのように部分列を選んだらまだ数えられてない部分列(ここで数えるべき部分列)になるかというと、
$m$ の中から少なくとも1つの要素を選んだ場合
です。
$l$ の要素は、 $x$ を使用した場合でも $y$ を使用した場合でも、その数字より左側に、 $r$ はどちらの場合でも右側に存在します。
ですが、 $m$ にある要素は、 $x$ を使用した場合は $x$ の右側に、 $y$ を使用した場合では $y$ の左側に並ぶことになりますので、かならずまだ数えられてない、新しい部分列を作成できます。
$m$ の中から少なくとも1つの要素を選ぶことについて考えると、
$l,m,r$ 全て使うパターン、 $m,r$ を使うパターン、 $l,m$ を使うパターン、 $m$ のみ使うパターンの4通りです。
これをそれぞれ求めるのは難しいので、 $l,m,r$ の中から自由に選ぶパターンから、余分なパターンを引く、包除原理の考え方を使うことにします。
$l,m,r$ の中から自由に選ぶパターンの計算式をたてます。すでに決まっているのは $y$ のみなので、 $l,m,r$ から残りの $k-1$ 個を選択します。 $l,m,r$ の個数をその文字で表現したとき、
$_{(l+m+r)}C_{(k-1)}$ となります。
そして、余分なパターンは、 $m$ を使用しないパターンです。これは言い換えると、 $l,r$ のみから選んだパターン、となります。
$l,r$ から自由に選ぶパターンは、簡単に計算することができ、
$_{(l+r)}C_{(k-1)}$ です。あとは、上の式から下の式を引くだけでよく、
$_{(l+m+r)}C_{(k-1)} - _{(l+r)}C_{(k-1)}$ となります。

ということで、最終的な式は次のようになります。
$_nC_k + _{(n-1)}C_{(k-2)} + _{(l+m+r)}C_{(k-1)} - _{(l+r)}C_{(k-1)}$
あとは、それぞれの $k$ についてこれを求めれば、答えとなります。