[b6e0OJ]和积和III
测试数据来自 b6e0_OJ/1014
题目描述
给定拥有\(n\)个数的序列\(A\)。定义\(f(k)\)表示在序列\(A\)中找出拥有\(k\)个元素的子序列(元素相同但位置不同的算多次),并将它们的积求和。
例如,当\(A=\){\(2,3,4\)},\(f(2)=26\)。原因如下: 所有的长度为\(2\)的子序列共有3个,分别是{\(2,3\)},{\(2,4\)},{\(3,4\)},它们的乘积之和为\(2\times3+2\times4+3\times4=26\)。
现在,凉心的Ducati会\(q\)次询问你\(\sum_{l=x}^y\sum_{r=l}^y\sum_{i=l}^{r}f(i)\)的值。这个式子的值等价于如下伪代码片段:
for l=x~y
for r=l~y
for i=l~r
f(i)的和;
由于答案可能过大,请将答案对\(1000000007(10^9+7)\)取模。
输入格式
第一行输入\(n\)和\(q\),表示序列中元素的个数与询问的次数。
第二行输入\(n\)个数,表示序列\(A\)的\(n\)个元素。
下面输入\(q\)行,每行两个整数\(x\)和\(y\),表示询问\(\sum_{l=x}^y\sum_{r=l}^y\sum_{i=l}^{r}f(i)\)的值。
输出格式
输出\(q\)行,第\(i\)行为第\(i\)个询问的答案。
输入输出样例
输入
3 2
1 2 3
1 1
2 3
输出
6
34
样例解释
首先,得到\(f(1)=6,f(2)=11,f(3)=6\)。
第一个询问是求\(f(1)\),即\(6\)。
第二个询问是求\(f(2)+(f(2)+f(3))+f(3)\),即\(34\)。
数据范围
对于100%的数据,\(1\le n,q\le1000\),\(1\le a_i≤10^9\),\(x\le y\)。
Subtask 1(10%): \(x=y\)。
Subtask 2(20%): \(n,q\le5\)。
Subtask 3(20%): \(n,q\le100\)。
Subtask 4(10%): \(a_i≤1000\)。
Subtask 5(40%): 无特殊限制。
贡献者
题面:Ducati
数据,核题:b6e0
信息
- ID
- 1048
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者