最大和数列
问题描述
给定一个长为 m的序列b
你需要构造出一个序列A满足：对于所有 1≤i≤m，i 在 A 中出现了bi次
定义f(A) 的值如下：
求满足条件的 f(A)的最大值，及在取最大值时有多少种序列 A
输入
输入第一行包含一个整数m（1≤m≤5⋅10^5）--数组b的大小。
第二行包含m个整数b1,b2,...,bm（1≤ci≤106）--数组b。
输出
打印两个整数--f(A)的最大可能值和有此值的数组A的数量。
由于两个答案都可能太大，所以打印它们的模数对10^9+7取模；
输入例子 1
6 1 1 1 1 1 1
输出例子 1
0 720
输入例子 2
1 1000000
输出例子 2
499833345 1
输入例子 3
7 123 451 234 512 345 123 451
输出例子 3
339854850 882811119
提示
在第一个例子中，所有可能的数组A都是[1, 2, 3, 4, 5, 6]的排列组合。
最大值f(A)=0，有6！=720个这样的数组。
先考虑单个元素k，它有x个，它在A中的位置位{p1,…,px}。
具体地，我们可以举一个实例：设该元素出现的位置是 {2,3,5,8,9}
于是该元素对f(A) 的贡献是 (3-2)+(5-2)+(8-2)+(9-2)+(5-3)+(8-3)+(9-3)+(8-5)+(9-5)+(9-8)(3−2)+(5−2)+(8−2)+(9−2)+(5−3)+(8−3)+(9−3)+(8−5)+(9−5)+(9−8)。
化简可以得到，2被减了 4 次，3 被减了 2 次，5 被抵消，8 被加了 2 次，9 被加了 4 次。
更进一步推广，我们可以得到该元素对 f(A) 的贡献就是 p1(1-x)+p2(3-x)+……+p_x(x-1)
发现系数是一个公差为2首相为1-x的等差数列。大。
那么现在考虑n个元素。我们发现是n个等差为2的等差数列。然后你需要合理分配这些数 到pi上，使得答案最大。
事实上，我们并不需要把这个序列生成出来。我们可以使用一个差分数组，存储每个元素在序列中出现的次数。。
那么能求出最大值后。求个数
因为在 A 中的不同元素中，有 cnt个元素为系数数组贡献了 p，所以可行的方案数就是这 cnt 个元素的排列数 cnt!。根据乘法原理，总方案数就是 cnt_1!cnt_2!......cnt_k!
答案
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
const int N=1e6+10;
int m,x;
ll fact[N],d[N<<1],ans,cnt=1,now;
ll ask(ll l,ll r){return ((r-l+1)*(l+r)/2)%mod;} //求l..r的和
int main()
{
fact[0]=1;
for (int i=1;i<N;i++)fact[i]=fact[i-1]*i%mod;
scanf("%d",&m);
for(int i=1;i<=m;i++){scanf("%d",&x);d[1000002-x]++,d[1000002+x]--;} //将d偏移
for(int i=2;i<N<<1;i++) {
d[i]+=d[i-2];
ans=(ans+ask(now+1,now+d[i])*(i-1000001))%mod;
now+=d[i],cnt=(cnt*fact[d[i]])%mod;
}
printf("%lld %lld",ans,cnt);
}
标签：周赛,cnt,OJ,最大值,元素,例子,数组,序列,第三场 From： https://www.cnblogs.com/hihopkc/p/16866155.html