概率 D P DP DP。 记 c n t i cnt_i cnti表示有多少个 a j = i a_j=i aj=i，再把 a i a_i ai离散化。 令 f i , j f_{i,j} fi,j表示当前取过 i i i个数，当前取到了 a j a_j aj的概率。 f i , j = f i − 1 , k ∗ c n t a i n − i + 1 f_{i,j}=f_{i-1,k}*\frac{cnt_{a_i}}{n-i+1} fi,j=fi−1,k∗n−i+1cntai A n s = ∑ f i , j ∗ c n t a i − 1 n − i Ans=\sum{f_{i,j}*\frac{cnt_{a_i}-1}{n-i}} Ans=∑fi,j∗n−icntai−1 转移用前缀和优化即可。 时间复杂度 O ( n 2 ) O(n^2) O(n2)
