题目背景
赌神 CYJian,他回来了!
题目描述
tomoo 决定与 CYJian 进行决斗!
已知 tomoo 有 N 张扑克牌,每张扑克牌有一个RP值Ai, CYJian 有M张扑克牌,每张扑克牌有一个RP值Bi。
CYJian 与 tomoo 将会各自从他们的牌里任意取一段连续区间的牌决斗,谁的区间内的牌的RP值的和更大,谁就赢了,请你帮忙求出 tomoo 赢的概率。
输入格式
- 第一行 2 个正整数 N,M
- 第二行 N 个正整数 Ai
- 第三行 M 个正整数 Bi
输出格式
一个数表示 tomoo 获胜的概率,如果答案可以表示成 QP 的形式,则输出 QP%998244353(不懂的左转P3811)
5 5
1 2 3 4 5
1 3 5 7 9
754229067
10 15
7 8 5 1 2 3 6 5 4 1
52 10 5 6 3 2 1 4 5 8 7 4 5 6 3
181952721
1 1
5
5
0
5 5
1254125 36521421 25362142 12514221 25362142
857412252 36322411 2236232 1254112 36224125
261761853
2 2
2 4
2 5
332748118
提示
样例解释
- 样例 3:不管怎么抽都是平均,胜率为 0
- 样例 5:共有 9 种方案,其中 3 次 tomoo 会赢,胜率为 1/3
数据范围
- 对于 20% 的数据,0<N,M≤50
- 对于另外 20% 的数据,∑i=1NAi≤106,∑j=1MBj≤106
- 对于100%的数据,0<N,M≤2000,0<Ai,Bi≤109