遠回りな回答をしてしまった。
http://codeforces.com/contest/846/problem/F
問題
N要素の数列Aに対し、2値L,R∈[1,N]を当確率で選ぶ。
L>Rの場合はL,Rを反転させよう。
この時A[L...R]登場するユニークな要素数の期待値を求めよ。
解法
左端Lに対し、各L≦R≦NのRのユニークな要素数の総和を数えていこう。
A[L...R]中ある数値xが最初に登場する位置がA[f(x)]=xだとする。
するとRがf(x)以上の場合にxによってユニークな要素数が1増えるので、全体で(N+1-f(x))通りだけ1増加する。
Lを固定したとき、このf(x)の総和が全体の値に加算される。
まずL=1の場合におけるf(x)をすべて求めておこう。
以後、Lをインクリメントする際のf(x)の総和の変化を考える。
インクリメント前にf(x)=Lだったxについて、f(x)はLの次に値xを持つ要素、例えばf(x)=next(L)とする。
そうするとf(x)の総和はnext(L)-Lだけ変化する。
int N; int A[1010101]; int nex[1010101]; int pos[1010101]; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d",&N); FOR(i,N) scanf("%d",&A[i]); FOR(i,1010001) pos[i]=N; for(i=N-1;i>=0;i--) { nex[i]=pos[A[i]]; pos[A[i]]=i; } ll tot=0; ll sum=0; FOR(i,1010000) sum+=N-pos[i]; FOR(i,N) { tot+=sum-1; sum-=nex[i]-i; } double pat=1.0*N*(N-1)/2.0; _P("%.12lf\n",(tot*2+N)/(1.0*N*N)); }
まとめ
もっと簡単な解法を取ってる人も多かった。