洛谷 U45568 赌神：决斗

题目描述

\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：复制

输出样例#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：复制

输出样例#3：复制

输入样例#4：复制

5 5

1254125 36521421 25362142 12514221 25362142

857412252 36322411 2236232 1254112 36224125

输出样例#4：复制

261761853

输入样例#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);

 }

巴特西