ultmaster edited 7 年前
题目自己看。
30 分到 70 分其实没啥区别，蒙特卡洛模拟都能过，精度控得好一点多交几发 70 分就稳了。此题 SPJ (Special Judge)，只要答案误差满足要求，输出多少位不作要求。
考虑 $f(i,j)$ 表示总共在掷了 $i$ 枚骰子的前提下，获得总点数为 $j$ 的方案数。那么当 $j$ 较大时，显然有：
$$f(i,j)=\sum_{k=1}^6 \frac{1}{6}f(i-1,j-k)$$
理由是，只有当掷了 $i-1$ 枚骰子时总点数为 $j-1,j-2,\ldots,j-6$ 才有可能达到 $f(i,j)$。而对于 $f(i-1,j-k)$，能达到 $f(i,j)$ 的概率恰好为 $\frac{1}{6}$。
当 $j$ 较小时，显然对于 $k>j$ 的情况是不可能的，判断一下就好了。
很遗憾，如果直接递归搜索的话复杂度是指数级别的，肯定会超时。我们可以采用记忆化搜索，即对于每个计算过的 $f(i,j)$ 都存在一个对应的 $g[i][j]$ 数组中。
程序一开始的时候，可以把 $g[i][j]$ 全部赋值为小于 0 的数。下次再计算某 $f(i,j)$ 如果发现已经计算过（$g[i][j]>0$），那么就不用再次计算了，直接返回结果就可以。那么这样的话，其实每一个 $f(i,j)$ 最多计算了一次，又因为这个计算是常数级别的，总复杂度就降到了 $O(n^2)$，足够通过本题。
事实上，还有一种更方便的直接从 $i=0,j=0$ 开始用两重 for 循环计算 $g[i][j]$ 的方法。这种 Bottom-up 的策略，我们一般称为 DP (Dynamic Programming)，有兴趣的同学可以自行上网查找相关资料，这里只给出核心代码：
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= 6 * n; ++j) {
for (int t = 1; t <= min(6, j); ++t)
g[i][j] += g[i - 1][j - t];
g[i][j] /= 6;
}
哦对了，此题还有一个坑点，就是当 $k>6n$ 的时候，直接输出 $0$ 就好了。