定义f[i][j]为投掷前i次骰子,总和为j的概率
其中,初始化状态f[0][0]=1.0
状态转移方程为f[i][j]=∑k=1a[i]f[i−1][j−k]
分别计算二者投掷前i次骰子,总和为j的概率,分别记为f[i][j1],g[i][j2]
赛诺与提纳里每天都要来一把七圣召唤,但是最近赛诺的骰子太差了,总是用不出技能,然后输给骰子很好的小提。于是赛诺放弃了打牌,决心要用骰子来与提纳里一决胜负。提纳里便找来妙论派的前辈做出特制的骰子用来和赛诺对决。每个特制骰子有固定的面数 k (2⩽k⩽8),每一面对应的点数分别为 1,2,…,k。
赛诺有 n (1⩽n⩽20) 个骰子,对于骰子 i (1⩽i⩽n),它的面数为 ai (2⩽ai⩽8),摇到每一面的概率都是 ai1。提纳里有 m (1⩽m⩽20) 个骰子,对于骰子 j (1⩽j⩽m),它的面数为 bj (2⩽bj⩽8),摇到每一面的概率都是 bi1。
赛诺和提纳里分别摇各自拥有的全部骰子,然后把骰子朝上那一面的点数相加,最后比较谁的点数和最大,大的获胜,相同平手,小的获败。赛诺和提纳里只摇一把,平手不会继续重摇,赛诺想知道他获胜的概率,你能帮帮他吗?
共三行,第一行包含两个正整数 n 和 m ,
第二行包含 n 个整数,表示 a0,a1,…,an−1,
第三行包含 m 个整数,表示 b0,b1,…,bm−1。
共一行,一个浮点数,表示赛诺获胜的概率,保留小数点后3位有效数字。
输入
1 3
8
2 3 4
输出
0.255
100%的数据:$1\leqslant n,m\leqslant 20,\ 2\leqslant a_i,b_i\leqslant 8$。