D: 11 - AtCoder Regular Contest 077
1～nの数で構成された、n+1個の数列が与えられる。この数列の中で、1～nはそれぞれ少なくとも1回以上は登場する。この時、長さ1～n+1の部分列で、異なる個数の総和を求めよ。
要はある数が一つだけダブっており、それ以外は全部1個づつ現れる数列である。これを以下の3パターンに分けてカウントする。(以下、長さkの部分列とする)
- ダブりの数を含まない場合 n-2Ck 通り
- ダブりの数を1個含む場合 n-2Ck-1通り * ダブリの数の選び方2通り
- ダブりの数を2個含む場合 n-2Ck-2 通り
ただし、2番については次のような場合をダブルカウントしている。
xxxxxxxxxx11yyyyyyyyyyyyyy
そこで、この数を引く。これは、ダブっている数の両側にある数列の個数をmとおくとmCk-1通りであり、この数を引けばよい。mは愚直に数えてもO(N)である。
全体で計算量はO(N)になる。
