c/c++语言开发共享BZOJ4373: 算术天才⑨与等差数列(线段树 hash?)

题意 “题目链接” Sol 正经做法不会,听lxl讲了一种很神奇的方法 我们考虑如果满足条件,那么需要具备什么条件 设mx为询问区间最大值,mn为询问区间最小值 1. mx mn = (r l) k 2. 区间和 = mn len + $frac{n (n 1)}{2} k$ 3. $text{ …


题意

题目链接

sol

正经做法不会,听lxl讲了一种很神奇的方法

我们考虑如果满足条件,那么需要具备什么条件

设mx为询问区间最大值,mn为询问区间最小值

  1. mx – mn = (r – l) * k

  2. 区间和 = mn * len + (frac{n * (n – 1)}{2} k)

  3. (text{立方和} = sum_{i = 1}^{len} (mn + (i – 1)k) ^2)

第三条后面的可以直接推式子推出来((sum_{i = 1}^n i^2 = frac{n(n+1)(2n+1)}{6}))

最后的/6可以直接乘一下然后ull自然溢出。

%ignore_pre_1%

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/605381.html

(0)
上一篇 2021年5月13日
下一篇 2021年5月13日

精彩推荐