四川省省建设厅网站,营销型网站报价,建设网站软件,深圳有什么好的企业网站解析
被蓝题虐了。#xff08;悲 确实不太难#xff0c;就是没往那边想。
考虑如果某个值的下标分别位 i1,i2,...,ini_1,i_2,...,i_ni1,i2,...,in 那么如何计算贡献。 每一个下标和前面统计时作为被减数#xff0c;和后面统计时作为减数#xff0c;所以 iki_kik …解析
被蓝题虐了。悲 确实不太难就是没往那边想。
考虑如果某个值的下标分别位 i1,i2,...,ini_1,i_2,...,i_ni1,i2,...,in 那么如何计算贡献。 每一个下标和前面统计时作为被减数和后面统计时作为减数所以 iki_kik 的贡献系数就是 (k−1)−(n−k)2k−n−1(k-1)-(n-k)2k-n-1(k−1)−(n−k)2k−n−1。 那么所有下标的统计次数其实就是一个公差为 2 的等差数列1−n,3−n,...,n−11-n,3-n,...,n-11−n,3−n,...,n−1。 那么现在问题就转化成了有若干个系数要求重排使得 ∑i×ai\sum i\times a_i∑i×ai 最大。 显然应该让系数升序排列这也必然符合了每一个数提供的系数必然从前往后递增的限制。 方案数就是有相同系数时其可以产生一个全排列的阶乘。
现在还有一个问题是系数加在一起是 101110^{11}1011 级别的无法直接统计。 利用等差数列的性质奇偶分别差分即可。
代码
//luogu
#includebits/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 N2e6100;
const int inf1e9;
const int mod1e97;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,k;
int o1e610;
int sum[N];
ll jc[N];
ll niv2(mod1)/2;
inline ll S(ll x,ll y){ return 1ll*(xy)%mod*(y-x1)%mod*niv2%mod;
}
signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifnread();for(int i1;in;i){int xread();sum[1-xo];sum[x-1o2]--;}jc[0]1;for(int i1;in;i) jc[i]jc[i-1]*i%mod;ll val0,num1,cnt0;for(int i2;ioo;i){sum[i]sum[i-2];numnum*jc[sum[i]]%mod;val(valS(cnt1,cntsum[i])*((i-omod)%mod))%mod;cntsum[i];}printf(%lld %lld\n,val,num);return 0;
}
/*
*/
