题目描述
\mathcal{tomoo}tomoo决定与\mathcal{CYJian}CYJian进行决斗！
已知\mathcal{tomoo}tomoo有\mathcal{N}N张扑克牌，每张扑克牌有一个\mathcal{RP}RP值\mathcal{A_i}Ai，\mathcal{CYJian}CYJian有\mathcal{M}M张扑克牌，每张扑克牌有一个\mathcal{RP}RP值\mathcal{B_i}Bi。
\mathcal{CYJian}CYJian与\mathcal{tomoo}tomoo将会各自从他们的牌里任意取一段连续区间的牌决斗，谁的区间内的牌的\mathcal{RP}RP值的和更大，谁就赢了，请你帮忙求出\mathcal{tomoo}tomoo赢的概率。
输入输出格式
输入格式：
- 第一行22个正整数\mathcal{N,M}N,M
- 第二行NN个正整数\mathcal{A_i}Ai
- 第三行MM个正整数\mathcal{B_i}Bi
输出格式：
一个数表示\mathcal{tomoo}tomoo获胜的概率，如果答案可以表示成\frac{P}{Q}QP的形式,则输出\frac{P}{Q}\%998244353QP%998244353（不懂的左转P3811）
输入输出样例
输入样例#1：
5 5
1 2 3 4 5
1 3 5 7 9
输出样例#1：
754229067
输入样例#2：
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
输出样例#2：
181952721
输入样例#3：
1 1
5
5
输出样例#3：
0
输入样例#4：
5 5
1254125 36521421 25362142 12514221 25362142
857412252 36322411 2236232 1254112 36224125
输出样例#4：
261761853
输入样例#5：
2 2
2 4
2 5
输出样例#5：
332748118
说明
样例解释
- 样例33：不管怎么抽都是平均，胜率为00
- 样例55：共有99种方案，其中33次tomoo会赢，胜率为1/31/3
数据范围
- 对于20\%20%的数据，0<N,M\le500<N,M≤50
- 对于另外20\%20%的数据，\sum_{i=1}^NA_i\le10^6,\sum_{j=1}^MB_j\le10^6∑i=1NAi≤106,∑j=1MBj≤106
- 对于100\%100%的数据，0<N,M\le2000,0<A_i,B_i\le10^90<N,M≤2000,0<Ai,Bi≤109
做法：
由于最多只有20002000个数，我们可以算出一个长度为N的数列，它共有(N+1)N/2个区间，也就是说最多只会有2001000个区间和，所以我们对于每一个数列，用一个数组将每一个区间和储存下来就好了。
然后将两个数组排序(其实排一个数组就行了),再枚举其中的一个数组，同时用尺取来统计答案。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 4007
#define LL long long
#define mo 998244353
using namespace std;
int n,m,tot1,tot2,a[N],b[N],sum;
LL qa[N],qb[N];
LL suma[N*N],sumb[N*N]; LL ksm(LL a,LL b){
LL q=,base=a;
while(b){
if(b&) q*=base,q%=mo;
base*=base;
base%=mo;
b>>=;
}
return q;
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]),qa[i]=qa[i-]+a[i];
for(int i=;i<=m;i++) scanf("%d",&b[i]),qb[i]=qb[i-]+b[i];
for(int i=;i<=n;i++){
for(int j=i;j<=n;j++)
suma[++tot1]=qa[j]-qa[i-];
}
for(int i=;i<=m;i++){
for(int j=i;j<=m;j++)
sumb[++tot2]=qb[j]-qb[i-];
}
sort(suma+,suma+tot1+);
sort(sumb+,sumb+tot2+);
int j=;
for(int i=;i<=tot1;i++){
while(suma[i]>sumb[j+]&&j+<=tot2) j++;
sum+=j;
if (sum>mo) sum-=mo;
}
LL g=n*(n+)/;
g=g*m%mo*(m+)%mo;
g=g*ksm(,mo-)%mo;
printf("%lld",sum*ksm(g,mo-)%mo);
}