[略解]
以下、n=i=1∑9diとします。
初めにS=(a1,a2,...an)と固定された時に、Sに対するスコアTがどのような文字式として表せるかを考えてみましょう。
多項式f(x)=i=1∏n(ai+1)の変数部分として考えられるものは2n−1個あります。
これらの集合をUとします。
たとえば、n=3の時は[a1a2a3,a1a2,a1a3,a2a3,a1,a2,a3]の7個がそれにあたります。
この時、T=x∈U∑C(x)∗xの形で表せることは明らかです。
(但しC(x)は変数の取り方それぞれに依存したある整数係数)
また、これらのC(x)の係数部分の計算は各変数の取り方に対して、それぞれO(n)で行うことができます。(計算法は自分で考えてみてください)
すなわち、すべてのC(x)の計算をO(n2n)行うことができます。
ここまで来れば残りは簡単です。適切に状態量をまとめた動的計画法を実行することで全てのSに対するTの期待値の総和をO(n2)程度で実現できます。(計算法は自分で考えてみてください)
全体での計算量はO(n2n)です。
ちなみに、Sとしてありうる種類数は大雑把に見積もって最悪O(n!)程度あるため、全部試す方法では実行時間制限に収まらないです。