当前位置:网站首页>区间乘积的因子数之和——前缀和思想+定一移二
区间乘积的因子数之和——前缀和思想+定一移二
2022-07-01 11:51:00 【hans774882968】
作者:hans774882968以及hans774882968
题目
(sorry没找到原题链接~)有一个数组a
,长度≤1e5,1 <= a[i] <= 3
。设区间[l,r]
的权值为区间元素乘积的因数个数,求所有区间的权值和,模1e9+7
。
思路
区间权值为(区间2的个数 + 1) * (区间3的个数 + 1)
,这两个量可以用前缀和表示,不妨设为s2, s3
。则所求为
∑ l = 0 r − 1 ( s 2 [ r ] − s 2 [ l ] + 1 ) ∗ ( s 3 [ r ] − s 3 [ l ] + 1 ) \sum_{l=0}^{r-1} (s2[r]-s2[l]+1)*(s3[r]-s3[l]+1) l=0∑r−1(s2[r]−s2[l]+1)∗(s3[r]−s3[l]+1)
我们枚举r
,则认为r
是固定的,而l
是变化的。拆开得
r ∗ s 2 [ r ] ∗ s 3 [ r ] − s 2 [ r ] ∗ ∑ s 3 [ l ] + r ∗ s 2 [ r ] − s 3 [ r ] ∗ ∑ s 2 [ l ] + ∑ s 2 [ l ] ∗ s 3 [ l ] − ∑ s 2 [ l ] + r ∗ s 3 [ r ] − ∑ s 3 [ l ] + r r*s2[r]*s3[r] - s2[r]*\sum s3[l] + r*s2[r] - s3[r]*\sum s2[l] + \sum s2[l]*s3[l] - \sum s2[l] + r*s3[r] - \sum s3[l] + r r∗s2[r]∗s3[r]−s2[r]∗∑s3[l]+r∗s2[r]−s3[r]∗∑s2[l]+∑s2[l]∗s3[l]−∑s2[l]+r∗s3[r]−∑s3[l]+r
除了s2, s3
之外,还需要维护sum(s2[i]), sum(s3[i]), sum(s2[i]*s3[i])
这3个前缀和数组。
代码每次会生成一组随机数据,多次运行都对拍通过,我们就认为n^2
暴力和正解都正确实现了。
import random
mod = int(1e9) + 7
def data_gen(n):
return [random.randint(1, 3) for _ in range(n)]
def bf(a):
n = len(a)
ans = 0
for i in range(n):
v2, v3 = 0, 0
for j in range(i, n):
v2 += (a[j] == 2)
v3 += (a[j] == 3)
ans = (ans + (v2 + 1) * (v3 + 1) % mod) % mod
return ans
def solve(a):
n = len(a)
s2, s3 = [0], [0]
for v in a:
s2.append(s2[-1] + (v == 2))
s3.append(s3[-1] + (v == 3))
ss2, ss3, s23 = [0], [0], [0]
for i in range(1, n + 1):
ss2.append((ss2[-1] + s2[i]) % mod)
for i in range(1, n + 1):
ss3.append((ss3[-1] + s3[i]) % mod)
for i in range(1, n + 1):
s23.append((s23[-1] + s2[i] * s3[i] % mod) % mod)
ans = 0
for r in range(1, n + 1):
u = ((r * s2[r] * s3[r] % mod - s2[r] * ss3[r - 1] % mod +
r * s2[r] % mod - s3[r] * ss2[r - 1] % mod +
s23[r - 1] - ss2[r - 1] + r * s3[r] % mod -
ss3[r - 1] + r) % mod + mod) % mod
ans = (ans + u) % mod
return ans
if __name__ == '__main__':
a = [2, 1, 3]
ans1 = solve(a)
ans2 = bf(a)
assert ans1 == 13 and ans2 == 13
a = data_gen(2000)
ans1 = solve(a)
ans2 = bf(a)
assert ans1 == ans2
print(a[:20], ans1, ans2)
边栏推荐
- 印象深刻的bug汇总(持续更新)
- ES6 promise Usage Summary
- C knowledge point form summary 2
- Nordic nrf52832 flash 下载M4错误
- No statements may be issued when any streaming result sets are open and in use on a given connection
- redis中value/list
- VScode快捷键(最全)[通俗易懂]
- ABBIRB120工业机器人机械零点位置
- Epoll introduction
- 使用set_handler过滤掉特定的SystemC Wraning &Error Message
猜你喜欢
On recursion and Fibonacci sequence
S7-1500PLC仿真
Explore the contour detection function findcontours() of OpenCV in detail with practical examples, and thoroughly understand the real role and meaning of each parameter and mode
C knowledge point form summary 2
自组织是管理者和成员的双向奔赴
Compile and debug net6 source code
Binary stack (I) - principle and C implementation
About keil compiler, "file has been changed outside the editor, reload?" Solutions for
邻接矩阵无向图(一) - 基本概念与C语言
Learning summary on June 28, 2022
随机推荐
Exposure: a white box photo post processing framework reading notes
超详细黑苹果安装图文教程送EFI配置合集及系统
深入理解 grpc part1
JS date format conversion method
sshd_config 中 PermitRootLogin 的探讨
Cann operator: using iterators to efficiently realize tensor data cutting and blocking processing
自定義 grpc 插件
CPI tutorial - asynchronous interface creation and use
2022/6/30学习总结
Value/hush in redis
自定义 grpc 插件
redis中value/SortedSet
如何看懂开发的查询语句
redis常识
Flip the array gracefully
Personnaliser le plug - in GRPC
Mechanism and type of CPU context switch
Tianrunyun, invested by Tian Suning, was listed: its market value was 2.2 billion Hong Kong, and its first year profit decreased by 75%
Shangtang entered the lifting period: the core management voluntarily banned and strengthened the company's long-term value confidence
构建外部模块(Building External Modules)