Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad) D. Divide and Sum (思维,数学,逆元)

题意:有一个长度为\(2n\)数组,从中选分别选\(n\)个元素出来组成两个序列\(p\)和\(q\),(\(p\)和\(q\)中只要有任意一个元素在\(a\)的原位置不同,就算一个新的情况),选完后对\(p\)非降序排序,对\(q\)非升序排序,然后求它们每个元素对应位置的差的绝对值之和\(re s=\sum^{n}_1 |x_i-y_i|\),问所有情况的res总和.
题解:观察样例,不难发现,因为\(p\)非降序,\(q\)非升序,所以无论\(p\)和\(q\)怎么选,它们的贡献永远是排序后的后\(n\)个数之和减前\(n\)个数之和,证明可以去看这个:https://www.luogu.com.cn/blog/taskkill-SB/solution-cf1444b

所以我们要求的答案就是\((\sum^n_1 |x_i-y_i|)*C^n_{2n}\).用逆元算一下即可.感觉自己对需要取模求逆元的题目还是十分的不熟练啊.

代码:

int n;

int a[N];

int fac[N],inv[N];

int ans;

int fpow(int a,int k){

    int res=1;

    while(k){

        if(k&1) res=res%mod*a%mod;

        k>>=1;

        a=a%mod*a%mod;

    }

    return res;

}

signed main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n;

    for(int i=1;i<=2*n;++i) cin>>a[i];

    sort(a+1,a+1+2*n);

    fac[0]=1;

    for(int i=1;i<=2*n;++i){

        fac[i]=fac[i-1]%mod*i%mod;

        inv[i]=fpow(fac[i],mod-2);

    }

    int invC=fac[n<<1]*inv[n]%mod*inv[n]%mod;

    for(int i=1;i<=n;++i){

        ans=(ans-invC*a[i]%mod)%mod;

    }

    for(int i=n+1;i<=2*n;++i){

        ans=(ans+invC*a[i]%mod)%mod;

    }

    cout<<(ans+mod)%mod<<'\n';

    return 0;

}

巴特西

Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad) D. Divide and Sum (思维,数学,逆元)

最新文章

热门文章