[略解]

以下、n=i=19din = \displaystyle\sum_{i = 1}^{9} d_iとします。

初めにS=(a1,a2,...an)S = (a_1, a_2, ... a_n)と固定された時に、SSに対するスコアTTがどのような文字式として表せるかを考えてみましょう。

多項式f(x)=i=1n(ai+1)f(x) = \displaystyle \prod_{i = 1}^{n} (a_i + 1)の変数部分として考えられるものは2n12^n - 1個あります。

これらの集合をUUとします。

たとえば、n=3n = 3の時は[a1a2a3,a1a2,a1a3,a2a3,a1,a2,a3][a_1a_2a_3, a_1a_2, a_1a_3, a_2a_3, a_1,a_2,a_3]77個がそれにあたります。

この時、T=xUC(x)xT = \displaystyle \sum_{x \in U} C(x) * xの形で表せることは明らかです。

(但しC(x)C(x)は変数の取り方それぞれに依存したある整数係数)

また、これらのC(x)C(x)の係数部分の計算は各変数の取り方に対して、それぞれO(n)O(n)で行うことができます。(計算法は自分で考えてみてください)

すなわち、すべてのC(x)C(x)の計算をO(n2n)O(n 2^n)行うことができます。

ここまで来れば残りは簡単です。適切に状態量をまとめた動的計画法を実行することで全てのSSに対するTTの期待値の総和をO(n2)O(n^2)程度で実現できます。(計算法は自分で考えてみてください)

全体での計算量はO(n2n)O(n 2^n)です。

ちなみに、SSとしてありうる種類数は大雑把に見積もって最悪O(n!)O(n!)程度あるため、全部試す方法では実行時間制限に収まらないです。