F
题目:给定一个数组a,求出给定公式的的值;
看题目的公式,通过观察发现公式的值与a数组的顺序无关,所以首先将a数组按照从小到大排序;
假设 < ,考虑最大值对答案的贡献:
对于每个x:
1.考虑~的方案数:
因为<,当最大值时,~ 可以随便选;
所以方案数就是:, 记为.
2.考虑~的方案数:
因为 < ,当最大值时,~可以在[1, x]中取值,那么只要保证~中至少有一个是x就
满足啦,所以根据容斥定理,方案数就是,在~中选择一个数等于x,剩下的数字在[1,x]中取,减去选2个,加上选3个,
减去选4个......,这样得到的答案就是:
需要观察一下,你会发现上面的式子,是的一部分,那么化简一下就是下面的式子:
我们记为 f(x);
3.综上最大值x的贡献为: ;
所以对于每一段 < ,我们求得就是
化简一下:
记做:.
枚举x = 0到x = n - i + 1,求出n - i + 2个点值,然后做拉格朗日插值;
是拉格朗日插值后的结果;
当时, ;
所以最后ans =
红线标记的部分估计是大多数像我一样的菜鸡所需要学习的,那我们就继续学习吧!!!
什么是拉格朗日插值法:对于给定的几个点,找到关于这几个点的函数;
对于给定的若n+1个点,对应于它们的次数不超过n的拉格朗日多项式 只有一个;
看啦这么多,实际上就是套下模板嘛。。。。
实际上模板只要传入要求的点,就能求出相应相的值;
附上我写了很久的代码吧
#include #define ll long long using namespace std; const ll MOD = 1e9 + 7; struct PolyInter { int mod_, deg; vector inv, val, buf; void init(const vector& v, int m = 0) //预先计算逆元; { mod_ = m, deg = v.size(), val = buf = v; inv.resize(max(2, deg)); inv[1] = 1; for (int i = 2; i < deg; i++) { inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; } } ll eval(ll n) { ll b = 1; for (int i = 1; i < deg; i++) { b = b * (n - i + 1 + MOD) % MOD * inv[i] % MOD; buf[i] = b * val[i] % MOD; } b = 1; ll result = buf[deg - 1]; for (int i = deg - 2; i >= 0; i--) { b = (MOD - b) * inv[deg - 1 - i] % MOD * (n - i - 1 + MOD) % MOD; result = (result + buf[i] * b)% MOD; } return result; } }; ll pow(ll a, ll b) //快速幂a^n; { ll ans = 1; while(b) { if (b & 1) { ans = ans * a % MOD; } a = a * a % MOD; b >>= 1; } return ans; } int main() { int n; while (~scanf("%d", &n)) { vector a(n+1); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a.begin()+1, a.end()); ll result = 0; ll pre = 1, prev = 0; for (int i = 1; i <= n; i++) { if(a[i] == prev) continue; int exp = n - i + 1; vector vals(exp + 2); vals[0] = 0; for (int j = 1; j <= exp+1; j++) vals[j] = (MOD + (j*((pow((ll)j, (ll)exp) - pow((ll)(j-1), (ll)exp))%MOD)%MOD) + vals[j-1])%MOD; PolyInter p; p.init(vals); result = (result + pre*(p.eval(a[i]) - p.eval(prev))%MOD)%MOD; pre = pre * a[i] % MOD; prev = a[i]; } printf("%lld\n", (result+MOD)%MOD); } }
最后附上我的博客链接希望大家不要吐槽我!!!
全部评论
(0) 回帖