CF2224D&2223B Zhily and Barknights 题解

· · 题解

节选自 CF 2224 Div.2 总结。

呜哇，赛时没想出来赛后一眼秒了，我赛时和赛后是不用的是两个不同的脑子 /yun

诶诶诶等下，我好像没脑子来着。

关键在于没有直接把全部的当做计数最后再除总数，输输输。

我们考虑分开统计，对于一个 c_i，定义其能对逆序对数量带来的贡献为满足 j > i 但 c_j < c_i 的 j 个数（之和）。

那不就等价于，枚举 a_i \times b_j，找到所有 k > i 且 l \not= j 的满足 a_k \times b_l < a_i \times b_j 的个数嘛！

如果不考虑 l \not= j 这条限制，我们就可以直接离散化后树状数组做完了。

但是加上了这个限制怎么办呢？可以先忽略限制算出一个答案，最后再把那些 l = j 的情况，即 a_k < a_i 时所带来的贡献减掉不就行了嘛。

注意，这里算出来的是所有情况下的逆序对数量之和，最后逆元变成期望即可。

然后就做完啦，时间复杂度是 O(n^2 \log{n^2}) 的，瓶颈在于离散化和树状数组喵。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2005;
const int N2 = N*N;
const LL MOD = 998244353;
LL T,n,a[N],b[N];
LL p[N2],Ls[N2],cnt;
LL c[N2],Ans;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
void upd(LL x){while(x<=cnt)c[x]++,x+=x&-x;return;}
LL ask(LL x){LL sum=0;while(x)sum+=c[x],x-=x&-x;return sum;}
LL QP(LL x,LL y=MOD-2){
    LL as=1;
    while(y){
        if(y&1)as=as*x%MOD;
        x=x*x%MOD,y>>=1;
    }return as;
}
int main(){
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)b[i]=read();
        cnt=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                p[++cnt]=a[i]*b[j],Ls[cnt]=p[cnt];
        sort(Ls+1,Ls+cnt+1);
        cnt=unique(Ls+1,Ls+cnt+1)-Ls-1;
        for(int i=1;i<=n*n;i++)
            p[i]=lower_bound(Ls+1,Ls+cnt+1,p[i])-Ls;
        Ans=0;
        for(int i=0;i<=cnt;i++)c[i]=0;
        for(int i=1,l=n*(n-1)+1,r=n*n;i<=n;i++,l-=n,r-=n){
            for(int x=l;x<=r;x++)
                Ans=(Ans+ask(p[x]-1))%MOD;
            for(int x=l;x<=r;x++)upd(p[x]);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<i;j++)
                if(a[j]>a[i])Ans=(Ans+MOD-n)%MOD;
        Ans=Ans*QP(n*(n-1))%MOD;
        cout<<Ans<<"\n";
    }
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！