解析

被藍題虐了。（悲
確實不太難，就是沒往那邊想。

考慮如果某個值的下標分別位 $i_1,i_2,...,i_n$ 那么如何計算貢獻。
每一個下標和前面統(tǒng)計時作為被減數(shù)，和后面統(tǒng)計時作為減數(shù)，所以 $i_k$ 的貢獻系數(shù)就是 $(k?1)?(n?k)=2k?n?1$。
那么所有下標的統(tǒng)計次數(shù)其實就是一個公差為 2 的等差數(shù)列：$1?n,3?n,...,n?1$。
那么現(xiàn)在問題就轉(zhuǎn)化成了，有若干個系數(shù)，要求重排使得 $\sum i\times a_i$ 最大。
顯然應該讓系數(shù)升序排列，這也必然符合了每一個數(shù)提供的系數(shù)必然從前往后遞增的限制。
方案數(shù)就是有相同系數(shù)時其可以產(chǎn)生一個全排列的階乘。

現(xiàn)在還有一個問題是系數(shù)加在一起是 $10^{11}$ 級別的，無法直接統(tǒng)計。
利用等差數(shù)列的性質(zhì)，奇偶分別差分即可。

代碼

//luogu #include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") using namespace std;const int N=2e6+100; const int inf=1e9; const int mod=1e9+7; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,k; int o=1e6+10; int sum[N]; ll jc[N]; ll niv2=(mod+1)/2; inline ll S(ll x,ll y){ return 1ll*(x+y)%mod*(y-x+1)%mod*niv2%mod; } signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();for(int i=1;i<=n;i++){int x=read();sum[1-x+o]++;sum[x-1+o+2]--;}jc[0]=1;for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;ll val=0,num=1,cnt=0;for(int i=2;i<=o+o;i++){sum[i]+=sum[i-2];num=num*jc[sum[i]]%mod;val=(val+S(cnt+1,cnt+sum[i])*((i-o+mod)%mod))%mod;cnt+=sum[i];}printf("%lld %lld\n",val,num);return 0; } /* */

總結

以上是生活随笔為你收集整理的CF1612G Max Sum Array的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。