龙与地下城

龙与地下城

测试数据来自 system/2039

描述

小Q同学是一个热爱学习的人,但是他最近沉迷于各种游戏,龙与地下城就是其中之一。

在这个游戏中,很多场合需要通过掷骰子来产生随机数,并由此决定角色未来的命运,因此骰子堪称该游戏的标志性道具。

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

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

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

除此之外还有一些性质:

WW的一阶原点矩(期望)为ν1(W)=E(W)=i=0X1iP(W=i)=(X1)/2\nu_1(W)=E(W)=\sum\limits_{i=0}^{X-1}iP(W=i)=(X-1)/{2}

WW的二阶中心矩(方差)为μ2(W)=E((WE(W))2)=i=0X1(iE(W))2P(W=i)=(X21)/12\mu_2(W)=E((W-E(W))^2)=\sum\limits_{i=0}^{X-1}(i-E(W))^2P(W=i)=(X^2-1)/{12}

言归正传,现在小Q同学面对着一个生命值为AA的没有防御的敌人,能够发动一次必中的YdXYdX攻击,显然只有造成的伤害不少于敌人的生命值才能打倒敌人。
但是另一方面,小Q同学作为强迫症患者,不希望出现overkill,也就是造成的伤害大于BB的情况,因此只有在打倒敌人并且不发生overkill的情况下小Q同学才会认为取得了属于他的胜利。

因为小Q同学非常谨慎,他会进行1010次模拟战,每次给出敌人的生命值AA以及overkill的标准BB,他想知道此时取得属于他的胜利的概率是多少,你能帮帮他吗?

格式

输入格式

第一行是一个正整数TT,表示测试数据的组数,

对于每组测试数据,

第一行是两个整数X,YX,Y,分别表示骰子的面数以及骰子的个数,

接下来1010行,每行包含两个整数A,BA,B,分别表示敌人的生命值AA以及overkill的标准BB

输出格式

对于每组测试数据,输出1010行,对每个询问输出一个实数,要求绝对误差不超过0.0135790.013579

也就是说,记输出为aa,答案为bb,若满足ab0.013579|a-b| \leq 0.013579,则认为输出是正确的。

本题提供 Special Judge。

样例1

样例输入1

1
2 19
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9

样例输出1

0.000002
0.000038
0.000364
0.002213
0.009605
0.031784
0.083534
0.179642
0.323803
0.500000

限制

10%10\% 的数据,X20X\le 20Y40Y\le 40XY10000000X^Y \le 10000000

15%15\% 的数据,X20X\le 20Y1600Y\le 1600

30%30\% 的数据,X20X\le 20Y8000Y\le 8000

10%10\% 的数据,X=2X=2Y200000Y\le 200000

对于 100%100\% 的数据,2X202\le X\le 201Y2000001\le Y\le 200000T10T \le 100AB(X1)Y0\le A\le B\le (X-1)^YY>800Y > 800 的数据不超过 2 组。

来源

SDOI 2017 Round2 Day1

信息

ID
1088
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者