题解 CF1612G Max Sum Array
pengyule
·
·
题解
本题可以积累一个较常见的套路。
对于每一个 c_i，考虑这 c_i 个数产生的贡献。如果设其在 a 中的下标为 x_j(j=1,2,...,c_i;x_j<x_{j+1})，则它们产生总贡献是
\sum_{1\le j<k\le c_i}(x_k-x_j)
化简得
\sum_{j=1}^{c_i}(2j-c_i-1)x_j
单个元素产生的贡献是 (2j-c_i-1)x_j，可以把括号中的看成权值。
由此，这所有 \sum c_i 个数的贡献从大到小排序，依次给予下标 n,n-1,...,1，既可以实现“大乘大”的贪心策略。
同时，对于第二问（方案数），权值相同的 l 个数可以全排列，产生 \times l! 的方案。
但这样的复杂度为 O(\sum c_i) 的。
考虑到实际有用的是权值的大小，可以建一个权值桶。对于每个 c_i，第 1-c_i,3-c_i,...,c_i-3,c_i-1 个桶都需要加 1。
从大到小枚举权值，照旧给桶里的数分配下标。
对于实现方面，统一加可以用差分（稍加改动）。
代码细节：权值会有负数，但绝对值不超过 $10^6$，可以先统一加上 $10^6$ 便于数组标记。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5,mod=1e9+7;
typedef long long ll;
ll n,m,val,ans=1,c[N],b[2][N],jc[N];
signed main(){
cin>>m;
for(int i=1;i<=m;i++)cin>>c[i],n+=c[i];
for(int i=1;i<=m;i++){
ll x=1e6+1-c[i],y=1e6+c[i]-1;
b[x&1][x]++,b[x&1][y+1]--;
}
jc[0]=1;
for(int i=1;i<=2e6;i++)b[0][i]+=b[0][i-1],b[1][i]+=b[1][i-1],jc[i]=jc[i-1]*i%mod;
for(int i=2e6;i;i--){
val=(val+(n+n+1-b[i&1][i])*b[i&1][i]/2%mod*((i-1000000)%mod+mod)%mod)%mod;
ans=ans*jc[b[i&1][i]]%mod;
n-=b[i&1][i];
}
cout<<val<<' '<<ans;
}
```
*文首所指的套路指的是从第一公式到第二公式的化简。*