2019牛客暑期多校训练营（第九场）C Inversions of all permutations

本文主要是介绍2019牛客暑期多校训练营（第九场）C Inversions of all permutations，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一个数组a，设r为a的某种排序，$t(r)$为r中逆序对的个数，问你$\sum b^{t(r)}$是多少

题解：

值不重复的时候，我们考虑第i大的数，它和前面i-1个数组成的逆序对的所有可能是0-（i-1）
那么答案就乘上$(1+b+b^2+...+b^{i-1})$
为什么是这么算的，因为假设b在倒数第三位，那么它所能创造的逆序对的个数就是2，同时它也只能在倒数第二位了，那么对于这种情况答案就是直接乘上$b^2$。
那么对于多值重复的时候，对于一个出现k次的数，它会多算0-(k-1)次，那么我们答案就除上k-1时候的答案即可，也就是这个数内部的答案多算了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int N=1e5+5;
ll ret[N],p[N],ans[N];
unordered_map<int,int>mp;
ll qpow(ll a,ll b)
{ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
int main()
{ll n,m;scanf("%lld%lld",&n,&m);ret[0]=p[0]=ans[0]=1;for(ll i=1;i<n;i++){ret[i]=ret[i-1]*m%mod;p[i]=(p[i-1]+ret[i])%mod;ans[i]=ans[i-1]*p[i]%mod;}int x;for(int i=1;i<=n;i++)scanf("%d",&x),mp[x]++;for(unordered_map<int,int>::iterator it=mp.begin();it!=mp.end();it++)ans[n-1]=ans[n-1]*qpow(ans[it->second-1],mod-2)%mod;printf("%lld\n",ans[n-1]);return 0;
}

这篇关于2019牛客暑期多校训练营（第九场）C Inversions of all permutations的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---