版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [SDOI2017] 龙与地下城" categories:
很有 OI 味的一道题
<!-- more -->小 Q 同学是一个热爱学习的人, 但是他最近沉迷于各种游戏, 龙与地下城就是其中之一
在这个游戏中, 很多场合需要通过掷骰子来产生随机数, 并由此决定角色未来的命运, 因此骰子堪称该游戏的标志性道具
骰子也分为许多种类, 比如 4 面骰、6 面骰、8 面骰、12 面骰、20 面骰, 其中 20 面骰用到的机会非常多. 当然, 现在科技发达, 可以用一个随机数生成器来取代真实的骰子, 所以这里认为骰子就是一个随机数生成器
在战斗中, 骰子主要用来决定角色的攻击是否命中, 以及命中后造成的伤害值. 举个例子, 假设现在已经确定能够命中敌人, 那么 $YdX$ (也就是掷出 $Y$ 个 $X$ 面骰子之后所有骰子显示的数字之和) 就是对敌人的基础伤害. 在敌人没有防御的情况下, 这个基础伤害就是真实伤害
众所周知, 骰子显示每个数的概率应该是相等的, 也就是说, 对于一个 $X$ 面骰子, 显示 $0, 1, 2,\dots ,X−1$ 中每一个数字的概率都是 $\frac {1}{x}$
更形式地说, 这个骰子显示的数 $W$ 满足离散的均匀分布, 其分布列为
| $W$ | $0$ | $1$ | $2$ | $\dots$ | $X-1$ |
|---|---|---|---|---|---|
| $P$ | $\frac{1}{X}$ | $\frac{1}{X}$ | $\frac{1}{X}$ | $\dots$ | $\frac{1}{X}$ |
除此之外还有一些性质
$W$ 的一阶原点矩(期望)为 $v1(W)=E(W)=\sum{i=0}^{X-1}iP(W=i)=\frac {X-1}{2}$
$W$ 的二阶中心矩(方差)为 $\mu2(W)=E((W-E(W))^2)=\sum{i=0}^{X-1}(i-E(W))^2P(W=i)=\frac {X^2-1}{12}$
言归正传, 现在小 Q 同学面对着一个生命值为 A 的没有防御的敌人, 能够发动一次必中的 $YdX$ 攻击, 显然只有造成的伤害不少于敌人的生命值才能打倒敌人. 但是另一方面, 小 Q 同学作为强迫症患者, 不希望出现 overkill, 也就是造成的伤害大于 $B$ 的情况, 因此只有在打倒敌人并且不发生 overkill 的情况下小 Q 同学才会认为取得了属于他的胜利
因为小 Q 同学非常谨慎, 他会进行 10 次模拟战, 每次给出敌人的生命值 $A$ 以及 overkill 的标准 $B$, 他想知道此时取得属于他的胜利的概率是多少, 你能帮帮他吗？
第一行是一个正整数 $T$, 表示测试数据的组数,
对于每组测试数据:
第一行是两个整数 $X$ , $Y$, 分别表示骰子的面数以及骰子的个数;
接下来 10 行, 每行包含两个整数 $A$ , $B$, 分别表示敌人的生命值 $A$ 以及 overkill 的标准 $B$
对于每组测试数据, 输出 10 行, 对每个询问输出一个实数, 要求绝对误差不超过 $0.013579$,
也就是说, 记输出为 $a$, 答案为 $b$, 若满足 $|a-b|\leq 0.013579$, 则认为输出是正确的
1
2 19
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0.000002
0.000038
0.000364
0.002213
0.009605
0.031784
0.083534
0.179642
0.323803
0.500000
对于 $100\%$ 的数据, $T \leq 10$, $2 \leq X \leq 20$, $1 \leq Y \leq 200000$, $0 \leq A \leq B \leq (X-1)Y$, 保证满足 $Y > 800$ 的数据不超过 $2$ 组
| 测试点编号 | $X$ | $Y$ | |
|---|---|---|---|
| 1 | $\leq20$ | $\leq40$ | $X^Y\leq10000000$ |
| 2, 3, 4 | $\leq20$ | $\leq1600$ | |
| 5, 6, 7, 8, 9, 10 | $\leq20$ | $\leq8000$ | |
| 11, 12 | $=2$ | $\leq200000$ | |
| 13, 14, 15, 16, 17, 18, 19, 20 | $\leq20$ | $\leq200000$ |
对于单次询问, 答案显然是
$$ \sum{k=A}^B[x^k]\left(\sum{i=0}^{X-1}\frac{1}{X}x^i\right)^Y $$
这个时间复杂度是 $O(XY\log(XY))$, 对于大数据来说不能接受
注意到本题对误差要求极为宽泛, 这提示我们寻找一些拟合的方法
由中心极限定理, 设 $n$ 个独立同分布的随机变量 $x_1,x_2,...,x_n$ 的均值 $E(x_i)=\mu$, 方差 $E((x_i-E(xi))^2)=\sigma^2\ne 0$, 则随机变量 $Y=\sum{i=1}^nx_i$ 的分布在 $n\to\infty$ 时服从 $N(n\mu,n\sigma^2)$
所以在 $XY$ 较大时我们可以用正态分布去拟合结果, 求解时直接上自适应 Simpson 积分即可