NC14731 逆序对题解

这是一道很明显的排列组合题

先看题，他叫我们求所有长度为n的01串的逆序对数之和

那么，我们可以考虑计算每个位置与它之前的位置所产生的贡献：

第1个位置一定不会与之前的位置产生贡献，所以可以不管

对于第x(x!=1)个位置，它要和它前面的位置产生贡献的话，那么这个位置上的数就一定得是0，而它前面的就一定得是1

我们考虑枚举第x个位置前面的有几个1，然后，计算出第i个位置产生的贡献，为：

不难发现，是常数，我们提取出来：

因为

所以原式变为:

又

所以原式变为：

设

因为由意义，

所以,

整理下：

由高斯求和：

注意到，这个式子可以直接求出，所以输出这个答案即可~

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
inline long long ksm(int x,long long y){
    int ans=1;
    while(y){
        if(y&1){
            ans=(1LL*ans*x)%mod;
        }
        x=(1LL*x*x)%mod;
        y>>=1;
    }
    return ans;
}
int main(){
    long long n,ans=0;
    cin>>n;
    long long L,R;
    if(n&1){
        L=n,R=(n-1)/2;
    }else{
        L=n/2,R=n-1;
    }
    L%=mod,R%=mod;
    L=(1LL*L*R)%mod;
    printf("%lld",(1LL*L*ksm(2,n-2))%mod);
    return 0;
}