題意

給出一個長為n的序列，對于這個序列的任意一個排列，求$\sum f_a$的值。

題解

我們枚舉每一個$a_i$然后，計算$a_i$出現了多少次，然后把$a_i?num$加入到ans里面。
考慮$a_i$什么時候出現。
$a_i$出現的位置前面的$a_j$必須嚴格小于$a_i$，這樣$a_i$才能被取到，而且$a_i$后面一定要有比它大的數，這樣才能$a_i$取到。
假設小于$a_i$的數有$m$個，那么$nu{m}_m={\sum }_{r=0}^m{C}_m^r?r!?(n?1?r)!$
整個的公式就是：
${\sum }_{i=1}^n{a}_i?nu{m}_i$
但這樣暴力求的話時間復雜度是$O(n^2)$，因此必須運用公式變換上述式子，可以證明$nu{m}_i$可以在$O(1)$的時間求出來，具體求解方法見下圖。

題解

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define pr(x) cout<<#x<<":"<<x<<endl const int maxn = 1e6+10; typedef long long ll; const ll mod = 1e9+7; ll a[maxn],fac1[maxn],fac2[maxn]; int n; int main(){scanf("%d",&n);for(int i = 0;i < n;++i)scanf("%lld",&a[i]);sort(a,a+n);fac1[0] = 1;fac2[n+1] = 1;fac2[n] = n;for(int i = 1;i <= n;++i)fac1[i] = fac1[i-1]*i%mod;for(int i = n-1;i >= 1;--i)fac2[i] = fac2[i+1]*i%mod;ll ans = 0;for(int i = 0,j = 1;i < n && a[i] != a[n-1];i = j){for(j = i;a[i] == a[j];j++);ll num = j-i;ans = (ans + num*((a[i]*fac1[n-i-1]%mod)*fac2[n-i+1]))%mod;}cout<<ans<<endl;return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的codeforces 938E MaxHistory 组合数学的全部內容，希望文章能夠幫你解決所遇到的問題。

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