題意：給你n個數字，求所有排列的fa的和：

對于一個排列來說，一開始fa為1，m=1，若a[m]<a[i] fa=fa+a[m]。

題解：我們考慮一個數的貢獻，若這個數能產生貢獻，則比這個數大的數都在這個數后面（包括相等），那么我們就可以得到如下能得到貢獻的數目。

意思為：從n個位置中挑出n-i+1（大于等于這個數的個數）個位置，這n-i+1個位置中這個數必須是第一位，其他數可以任意排列。然后把剩下的小于他的數插入剩下的空位。

化簡之后得到：

這樣就可以通過逆元O（logn）計算當前這個數的答案了，對于相同的數，只要乘上其個數就可以了。

AC代碼：

#include<stdio.h> #include<algorithm> #define mod 1000000007 using namespace std; typedef long long ll; ll a[1000005]; ll qmi(ll a,ll b) {ll ans=1;while(b){if(b%2)ans=(ans*a)%mod;a=(a*a)%mod;b/=2;}return ans; } int main() {ll n;scanf("%lld",&n);ll Ann=1;for(ll i=1;i<=n;i++)Ann=Ann*i%mod;for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+1+n);ll ans=0,now;for(ll i=1;i<=n;i=now){now=i;while(a[i]==a[now]&&now<=n)now++;if(now<=n)ans=(ans+Ann*qmi(n-i+1,mod-2)%mod*(now-i)%mod*a[i]%mod)%mod;}printf("%lld\n",ans); }

總結

以上是生活随笔為你收集整理的Codeforces 938E Max History [排列组合]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。