牛客小白赛60(F.被抓住的小竹)&61(E.排队)(数学+推公式）

---

前言

逆序对是典型题，常用统计数组内逆序对用树状数组。但是求排列中的总逆序对数量需要利用组合数学推导公式。

F.被抓住的小竹

原题戳这里

题意： 求区间长度[1, n]的所有满足i<=j&&pi>=pj的个数，与[1, n]的inv§的乘积之和。通俗的来说，就是在原来数组的基础上取任意<=n的区间进行排列后的所有逆序对的和。

下面就来推公式：
1.首先将复杂的柿子进行转化

2.将柿子拆分
假设区间长度取得len，那么能够取len个数作为i，那么j能够取得1，2，3…len个
求和得
3.那么知道了一个区间的贡献之后，枚举长度之后能够得到

4.求一个逆序对的贡献
这里是球盒模型，C(球+箱，箱),i,j两个数将其他所有的数分到三个箱子内，并且允许空箱，也就是C(n-2+3,3）=n*(n-1)/2。
5.总共有的逆序对个数
n个数里面选2个数作为i, j, (n-2)个数进行全排列。C(n,2) * (n-2)!个逆序对，那么总逆序对的贡献为
6.求答案

coding

ll qpow(ll a,ll b)
{
    ll res=1;
    while(b){
        if(b&1)res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res%mod;
}

ll fac[N],ifac[N];//阶乘和逆元的阶乘
void init()
{
    fac[0] = 1;
    for (int i = 1; i < 100000+10; i++)
        fac[i] = fac[i - 1] * i % mod;
    ifac[100000+10-1]=qpow(fac[100000+10-1],mod-2);
    for(int i=100000+10-1;i>=1;i--)
        ifac[i-1]=ifac[i]*i%mod;
}
 
ll C(int n,int m)
{
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
 
void solve()
{
    int n;
    scanf("%d",&n);
    ll ans=(((C(n+3,4)%mod*fac[n-2])%mod*(1ll*n*(n-1)/2)%mod)%mod*(1ll*n*(n-1)/2%mod))%mod;
    printf("%d\n",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

E.排队

题意： 求所给数组的所有排列的逆序对总数（注意这里会出现重复数字)

每两个不同的数字肯定会产生一对逆序对，那么先找逆序对的个数，再看逆序对的贡献
1.逆序对的个数：遍历当前数组，逆序对的个数就是i-（在i前面的和i相同的数字),记录一下当前数字已经有多少个就好了。
2.总排列数为n!,但是（ai,aj）只会产生一种逆序对，最后答案就是n!/2种，再乘不同数组的对数。
（其实可以将相同的数字放进同一个箱子里，但是每个箱子里的球编号不同，每次从不同的两个箱子里面取得两个球一定不相同)
coding

map<int,int>mp;
 
 void solve()
 {
    int n;
    scanf("%d",&n);
    ll ans=0;
    for(int i=1;i<=n;i++){
        int a;
        scanf("%d",&a);
        ans=(ans+i-(++mp[a]))%mod;
    }
    for(int i=3;i<=n;i++)
        ans=(ans*i)%mod;
    printf("%d\n",ans);
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结

复杂问题转化为简单问题逐步求解，化繁为简，以及模型转化，便于理解。