怎样查看网站是否备案,90设计网站官网入口,中国手工活加工官方网站,数据分析师岗位要求CF938E Max History
题意#xff1a;
我们定义f(a)为#xff1a;
1、开始时#xff0c;f(a)0,M1。
2、对于每个2in,如果a[M]a[i],那么f(a)f(a)a[M],Mi。
现在对于一个给定的数组a#xff0c;求其所有排列的f(a)之和#xff0c;答案对1e97取模。
题解
我们定义f(a)为
1、开始时f(a)0,M1。
2、对于每个2in,如果a[M]a[i],那么f(a)f(a)a[M],Mi。
现在对于一个给定的数组a求其所有排列的f(a)之和答案对1e97取模。
题解
计数问题组合数推导 经常用的组合恒等式 k∗Cnkn∗Cn−1k−1k * C_{n}^{k}n*C_{n-1}^{k-1}k∗Cnkn∗Cn−1k−1 Ckn∗CmkCmn∗Cm−nm−k(m−km−n)C_{k}^{n}*C_{m}^{k}C_{m}^{n}*C_{m-n}^{m-k}(m-km-n)Ckn∗CmkCmn∗Cm−nm−k(m−km−n) ∑i0nCni2n\sum_{i0}^{n}C_{n}^{i}2^n∑i0nCni2n ∑k0n∗(−1)kCnk0\sum_{k0}^{n}*(-1)^kC_{n}^{k}0∑k0n∗(−1)kCnk0 CnkCnk1Cn1k1C_{n}^{k}C_{n}^{k1}C_{n1}^{k1}CnkCnk1Cn1k1 ∑k0mCnkkCnm1m\sum_{k0}^{m}C_{nk}^{k}C_{nm1}^{m}∑k0mCnkkCnm1m 范德蒙德卷积 ∑i0kCniCmk−iCnmk\sum_{i0}^{k}C_{n}^{i}C_{m}^{k-i}C_{nm}^{k}∑i0kCniCmk−iCnmk
代码
#includebits/stdc.h
#define mod 1000000007
const int maxn 1000035;int n,ans,cnt,a[maxn],fac[maxn],inv[maxn];int read()
{char ch getchar();int num 0, fl 1;for (; !isdigit(ch); chgetchar())if (ch-) fl -1;for (; isdigit(ch); chgetchar())num (num1)(num3)ch-48;return num*fl;
}
int main()
{n read();for (int i1; in; i) a[i] read();std::sort(a1, an1);fac[0] fac[1] inv[0] inv[1] 1;for (int i2; in2; i){inv[i] mod-1ll*(mod/i)*inv[mod%i]%mod,fac[i] 1ll*fac[i-1]*i%mod;}for (int i1,j; in; ij1){for (ji; a[j1]a[i]; j);//J为 if (jn) break;//i-1是严格比他小的数 //n-j是严格大于他的数 //j-i1是与a[i]一样大的数量 cnt inv[n-i1];ans (1ll*ans1ll*a[i]*(j-i1)%mod*cnt%mod)%mod;}printf(%d\n,1ll*ans*fac[n]%mod);return 0;
}
