#271. #2267. 「SDOI2017」龙与地下城

#2267. 「SDOI2017」龙与地下城

说明

小 Q 同学是一个热爱学习的人,但是他最近沉迷于各种游戏,龙与地下城就是其中之一。 在这个游戏中,很多场合需要通过掷骰子来产生随机数,并由此决定角色未来的命运,因此骰子堪称该游戏的标志性道具。

骰子也分为许多种类,比如 4 面骰、6 面骰、8 面骰、12 面骰、20 面骰,其中 20 面骰用到的机会非常多。当然,现在科技发达,可以用一个随机数生成器来取代真实的骰子,所以这里认为骰子就是一个随机数生成器。

在战斗中,骰子主要用来决定角色的攻击是否命中,以及命中后造成的伤害值。举个例子,假设现在已经确定能够命中敌人,那么 YdXYdXYdX(也就是掷出 YYYXXX 面骰子之后所有骰子显示的数字之和)就是对敌人的基础伤害。在敌人没有防御的情况下,这个基础伤害就是真实伤害。

众所周知,骰子显示每个数的概率应该是相等的,也就是说,对于一个 XXX 面骰子,显示 0,1,2,,X1 中每一个数字的概率都是 1X\frac 1 XX1

更形式地说,这个骰子显示的数 WWW 满足离散的均匀分布,其分布列为

W W W 0 0 0 1 1 1 2 2 2 … \ldots X−1 X - 1 X1
P P P 1X \frac{1}{X} X1 1X \frac{1}{X} X1 1X \frac{1}{X} X1 … \ldots 1X \frac{1}{X} X1

除此之外还有一些性质

  • WWW 的一阶原点矩(期望)为

    v1(W)=E(W)=∑i=0X−1iP(W=i)=X−12 v_1(W) = E(W) = \sum ^{X-1} _{i=0} iP(W=i) = \frac{X-1}{2} v1(W)=E(W)=i=0X1iP(W=i)=2X1
  • WWW 的二阶中心矩(方差)为

    μ2(W)=E((W−E(W))2)=∑i=0X−1(i−E(W))2P(W=i)=X2−112 \mu_2(W) = E((W-E(W))^2) = \sum ^{X-1}_{i=0}(i-E(W))^2P(W=i) = \frac{X^2-1}{12} μ2(W)=E((WE(W))2)=i=0X1(iE(W))2P(W=i)=12X21

言归正传,现在小 Q 同学面对着一个生命值为 AAA 的没有防御的敌人,能够发动一次必中的 YdXYdXYdX 攻击,显然只有造成的伤害不少于敌人的生命值才能打倒敌人。但是另一方面,小 Q 同学作为强迫症患者,不希望出现 overkill,也就是造成的伤害大于 BBB 的情况,因此只有在打倒敌人并且不发生 overkill 的情况下小 Q 同学才会认为取得了属于他的胜利。
因为小 Q 同学非常谨慎,他会进行 10 次模拟战,每次给出敌人的生命值 AAA 以及 overkill 的标准 BBB,他想知道此时取得属于他的胜利的概率是多少,你能帮帮他吗?

</div> </div>

输入格式

第一行是一个正整数 TTT ,表示测试数据的组数。
对于每组测试数据,第一行是两个整数 XXXYYY,分别表示骰子的面数以及骰子的个数。
接下来 10 行,每行包含两个整数 AAABBB,分别表示敌人的生命值 AAA 以及 overkill 的标准 BBB

输出格式

对于每组测试数据,输出 10 行,对每个询问输出一个实数,要求绝对误差不超过 0.0135790.0135790.013579,也就是说,记输出为 aaa,答案为 bbb,若满足 ∣a−b∣≤0.013579|a-b| \leq 0.013579ab0.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%100\%100% 的数据,T≤10T \leq 10T102≤X≤202 \leq X \leq 202X201≤Y≤2000001 \leq Y \leq 2000001Y2000000AB(X1)Y ,保证满足 Y>800Y > 800Y>800 的数据不超过 2 组。

测试点编号 XXX YYY
1 ≤20\leq 2020 ≤40\leq 4040 XY≤107X^Y \leq 10^7XY107
2 ~ 4 ≤20\leq 2020 ≤1600\leq 16001600
5 ~ 10 ≤20\leq 2020 ≤8000\leq 80008000
11 ~ 12 =2= 2=2 ≤200000\leq 200000200000
13 ~ 20 ≤20\leq 2020 ≤200000\leq 200000200000