luogu#P4978. 赌神:决斗

    ID: 9002 远端评测题 2000ms 125MiB 尝试: 3 已通过: 0 难度: 4 上传者: 标签>二分答案枚举暴力前缀和概率论统计

赌神:决斗

题目背景

赌神 CYJian\mathcal{CYJian},他回来了!

题目描述

tomoo\mathcal{tomoo} 决定与 CYJian\mathcal{CYJian} 进行决斗!

已知 tomoo\mathcal{tomoo}N\mathcal{N} 张扑克牌,每张扑克牌有一个RP\mathcal{RP}Ai\mathcal{A_i}CYJian\mathcal{CYJian}M\mathcal{M}张扑克牌,每张扑克牌有一个RP\mathcal{RP}Bi\mathcal{B_i}

CYJian\mathcal{CYJian}tomoo\mathcal{tomoo} 将会各自从他们的牌里任意取一段连续区间的牌决斗,谁的区间内的牌的RP\mathcal{RP}值的和更大,谁就赢了,请你帮忙求出 tomoo\mathcal{tomoo} 赢的概率。

输入格式

  • 第一行 22 个正整数 N,M\mathcal{N,M}
  • 第二行 NN 个正整数 Ai\mathcal{A_i}
  • 第三行 MM 个正整数 Bi\mathcal{B_i}

输出格式

一个数表示 tomoo\mathcal{tomoo} 获胜的概率,如果答案可以表示成 PQ\frac{P}{Q} 的形式,则输出 PQ%998244353\frac{P}{Q}\%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

提示

样例解释

  • 样例 33:不管怎么抽都是平均,胜率为 00
  • 样例 55:共有 99 种方案,其中 33tomoo 会赢,胜率为 1/31/3

数据范围

  • 对于 20%20\% 的数据,0<N,M500<N,M\le50
  • 对于另外 20%20\% 的数据,i=1NAi106,j=1MBj106\sum_{i=1}^NA_i\le10^6,\sum_{j=1}^MB_j\le10^6
  • 对于100%100\%的数据,0<N,M2000,0<Ai,Bi1090<N,M\le2000,0<A_i,B_i\le10^9