\(\{ v_i \}\) は降順にソートする.

平均の最大値は \(A\) 先頭から \(A\) 個選んだときである. 平均は \(v_A\) 以上なので, \(v_{A+1}\) を追加して平均が上がることはない.

また, この平均になる組み合わせの数であるが \(v_1 \gt v_A\) ならば \(A\) 個選ぶ方法しかない. 先頭 \(A\) 個の平均は \(v_A\) より上なので, \(v_{A+1}\) を追加すると平均が下がるからである.

\(v_{A-a} = v_{A-a+1} = \dots = v_A = v_{A+1} = \dots = v_{A+b}\) だとすると, \(a+b+1\) 個から \(a+1\) 個を選ぶ組み合わせの数なので, \({}_{a+b+1}C_{a+1}\) 通りとなる.

\(v_1 = v_A\) のときは \(A\) 個以上選べる可能性がある.

\(v_1 = v_2 = \dots = v_A = v_{A+1} = \dots = v_k\) となっているとすると, この中から \(A\) 個を選ぶ組み合わせの数は \({}_kC_A\) である.

同様に, \(A+1\) 個を選ぶ組み合わせ, \(A+2\) 個を選ぶ組み合わせ… と計算していき, \(\min(k, B)\) 個を選ぶ組み合わせまで順に計算していき, 総和を求める.

なお, \({}_nC_r\) の値は \(10^{15}\) を超えないので, パスカルの三角形で計算しておく.