33OJ
登录 注册

#P17622. [qaswed12 OI R1] Function

    ID: 20185 远端评测题 2500ms 512MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>数学线段树O2优化最大公约数 gcd二项式定理

[qaswed12 OI R1] Function

题目描述

定义函数 ff 满足:

$$f(x)=\sum\limits_{i=0}^x{x\choose i}(-1)^{\gcd(x,i)}.$$

特别的,gcd⁡(x,0)=x\gcd(x,0)=x。


给定一个长度为 nn 的序列 AA。

有 mm 次操作,操作分为两种:

  1. 1 l r k,表示 ∀i∈[l,r],Ai←Ai+k\forall i\in[l,r],A_i\gets A_i+k。
  2. 2 l r,表示查询 ∑i=lrf(Ai)\sum\limits_{i=l}^r f(A_i)。

答案可能会比较大,请对 109+710^9+7 取模。

输入格式

第一行,两个正整数 n,mn,m。

第二行,nn 个整数,表示序列 AA。

接下来 mm 行,每一行表示一个操作,输入方式见题目描述。

输出格式

对于每个操作二,输出一行,一个非负整数表示答案。

6 5
1 1 4 5 1 4
2 1 6
1 2 4 3
1 3 6 1
2 2 6
2 3 4
999999969
999999463
999999495

提示

样例解释

第一次询问的实际答案为 −38.-38.

数据范围与说明

本题输入输出量较大,请使用较快的输入输出方式。

本题开启捆绑测试。

子任务编号 n,m≤n,m \le Ai,k≤A_i,k \le 特殊性质 分值
11 10210^2 5050 无 1010
22 5×1035\times 10^3 10310^3 ^ 1515
33 10510^5 A\text A
44 ^ B\text B
55 无 2020
66 10610^6 ^ 2525

特殊性质 A\text A:保证对于每次操作,满足 l=1,r=nl=1,r=n。

特殊性质 B\text B:保证对于每次操作一,满足 k=1k=1。

对于 100%100\% 的数据,满足 1≤n,m,Ai,k≤1061\le n,m,A_i,k \le 10^6,1≤l≤r≤n1 \le l \le r \le n。