贵阳网站制作 建设,施工企业会计分录大全,什么网站可以做实验室,网站开发平台 eclipse本场比赛难度不大#xff0c;也是本人第一次AK#xff0c;最后一题用组合数学推公式#xff0c;本篇博客主要讲解最后一题的思路 G-小红的陡峭值#xff08;五#xff09;#xff08;hard#xff09;_牛客周赛 Round 84 思路#xff1a;本题要我们求p/q mod M ,即p*也是本人第一次AK最后一题用组合数学推公式本篇博客主要讲解最后一题的思路 G-小红的陡峭值五hard_牛客周赛 Round 84 思路本题要我们求p/q mod M ,即p*q的逆q为排列数我们可以很容易得到即 n!但分子为所有排列的陡峭值之和暴力做法肯定是不行的于是我们可以通过绝对值的性质若a2a1,则|a1-a2||a2-a1|a2-a1先将数组a进行升序排序我们可以计算a[i-1]a[i]这对相邻元素会出现在多少种不同的排列中这里我们可以使用高中学的排列组合来计算从n个元素中拿出去2个元素还剩下n-2个元素那么这n-2个元素就有(n-2)!种摆放方式再将a[i-1]a[i]插入n-1个空中的任意一个就可以得到a[i-1]a[i]在n-2)!*(n-1)(n-1)!个排列中做出了贡献而a[i]a[i-1]的贡献与a[i-1]a[i]一样那么我们要计算出(a[i]-a[i-1])(a[i]-a[i-2])(a[i]-a[i-3])...(a[i]-a[1])的和那么这个式子化简一下就是(i-1)*a[i]-pre[i-1]最终我们得到的结果p/q
Code:
int n;int qmi(int a,int b)
{int res1;while(b){if(b1)resres*a%mod;b1;aa*a%mod;}return res;
}
void solve()
{cin n;vectorint v(n1);for(int i1;in;i) cinv[i];sort(v.begin()1,v.end());vectorint pre(n1,0);for(int i1;in;i) {pre[i](pre[i-1]v[i]%mod)%mod;}int S0;for(int i1;in;i){int b((v[i]%mod)*(i-1mod)%mod)%mod;b(b-pre[i-1]mod)%mod;S(Sb)%mod;}int num(2*S)%mod;int invqmi(n,mod-2);int ansnum*inv%mod;coutansendl;
}
