円環上に，\(A_i\) 個の \(i\) (\(1 \leq i \leq N\)) と \(1\) 個の \(\infty\) を並べてみます． \(\infty\) の位置で円環を切ることにすると列になるので，これは同じ問題です．

円環上の整数 \(i\) を \(1\) つ固定し，それの右隣が \(i\) 未満である確率を考えます． 固定されてない値は \(S\) 個あり，その内 \(\sum_{j<i} A_j\) 個が条件を満たすことになります．

よって求める確率は \(\sum_{1 \leq i \leq N} A_i (\sum_{1 \leq j < i} A_j)/S\) になります．

回答例(C++)