掷五个六面骰（面上分别标1至6），三个最大的点数之和为15的情况一共有1111种，以下是其中的一些例子： \begin{align*} D_1,D_2,D_3,D_4,D_5 &= 4,3,6,3,5\\ D_1,D_2,D_3,D_4,D_5 &= 4,3,3,5,6\\ D_1,D_2,D_3,D_4,D_5 &= 3,3,3,6,6\\ D_1,D_2,D_3,D_4,D_5 &= 6,6,3,3,3 \end{align*} 掷20个12面骰（面上分别标1至12），十个最大的点数之和为70的情况一共有多少种？

本题难度:

解答

从小到大依次枚举添加骰子，设$f(a,b,c,d)$是已有a个骰子，其中最大为c，c重复了b次，且从第11个骰子起之后所有骰子之和为d的情况总数。

考虑增加一个骰子：

若这颗骰子的点数x大于b，则$a\mapsto a+1$, $b:=1$, $c:=k$，d是否增加取决于a是否超过10，每种状态能生成$a+1$种新状态（最大值可以出现在任意位置上）。

若这颗骰子的点数x等于b，则$a\mapsto a+1$, $b\mapsto b+1$, d是否增加仍取决于a是否超过10，每种状态能生成$(a+1)/(b+1)$种新状态（考虑最大值出现的位置并去重）。

初值容易生成，递推计算即得结果$7448717393364181966$。

f=[[[[0]*71 for c in range(13)] for b in range(21)] for a in range(21)]

for j in range(1,13):
    f[1][1][j][0] = 1

for a in range(1,20):
    for b in range(1,a+1):
        for c in range(1,13):
            for d in range(71):
                if f[a][b][c][d]>0:
                    for x in range(c,13):
                        s=d if a < 10 else d+x
                        if s <= 70:
                            j=b+1 if x==c else 1
                            f[a+1][j][x][s]+=f[a][b][c][d]*(a+1)/j

print sum(f[20][j][k][70] for j in range(1,21) for k in range(1,13))