牛客月赛60 F.被抓住的小竹(数学&推式子)

牛客月赛60 F.被抓住的小竹(数学&推式子)

考虑枚举每个区间的贡献。

每个区间内所有的数都作为$x$一次时的贡献和。

因为要求区间内$\ge x$数个数， 那么区间内的数从小到大排序后，显然最大的数贡献是1、第二大的数贡献是2，依此内推。

因此对于长度为$len$的贡献是${\sum }_{i=1}^{len}i=\frac{len(len+1)}{2}$

因此我们可以枚举区间长度。

区间长度为$i$的个数为$n-i+1$。

所以总贡献是：$\sum _{i=1}^n(n-i+1)\times \frac{i(i+1)}{2}$然后展开化简一波。

$ans=\frac{n(n+1)(n+2)(n+3)}{24}$

是一个组合数的形式：$ans=C_{n+3}^4$与排列无关。

因此可以提出来，然后$res=ans\times {\sum }_{p}inv(p)$

求所有排列的逆序对和，可以这样考虑。

一共有$n!$个排列，对于一个两个数$i,j(i<j)$ 他们的贡献是对称的，也就是说有一半的$po{s}_i<po{s}_j$，另一半是$po{s}_i>po{s}_j$。因此贡献是$\frac{n!}{2}$。

所有有序对总数是$\frac{n(n-1)}{2}$

所以答案就是：$C_{n+3}^4\frac{n!n(n-1)}{4}=\frac{n^2\times (n+3)!\times (n-1)}{96}$

#include
using namespace std;
int mod=1e9+7;
long long power(long long a,long long b){
    long long res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
long long inv(int x){
    return power(x,mod-2);
}
long long jc[2020200];
int main(){
    jc[0]=1;
    int n,i,j,k;
    for(i=1;i<=1e5+10;i++)jc[i]=jc[i-1]*i%mod;
    cin>>k;
    while(k--){
        long long x;
        cin>>x;
        cout<<x*x%mod*(x-1)%mod*jc[x+3]%mod*inv(96)%mod<<'\n';
    }
}
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