会员专享
请先
登录 ，登录后可使用今日免费解锁；
开通会员 后可解锁完整内容。
解题思路
下标从 0 0 0
H ( d ) = ∑ i = 0 n − 1 ( i m o d d ) ⋅ v i , d = 1 , 2 , … , n , H(d)=\sum_{i=0}^{n-1}(i\bmod d)\cdot v_i,\qquad d=1,2,\ldots,n,
H ( d ) = i = 0 ∑ n − 1 ( i mod d ) ⋅ v i , d = 1 , 2 , … , n , 并对 1000000007 1000000007 1000000007 O ( n 2 ) O(n^2) O ( n 2 ) n ≤ 200000 n\le 200000 n ≤ 200000
把余数拆开：i m o d d = i − d ⋅ ⌊ i / d ⌋ i\bmod d=i-d\cdot\lfloor i/d\rfloor i mod d = i − d ⋅ ⌊ i / d ⌋
题目内容
江岸步道的灯阵调度室要把沿江一列彩灯做成「按闪烁周期」的亮度报表。步道上共有 n n n 0 依次排到编号 n − 1 n-1 n − 1 i i i v i v_i v i d d d i i i i i i d d d d = ‘ 1 ‘ , ‘ 2 ‘ , … , n d=`1`,`2`,\ldots,n d = ‘1‘ , ‘2‘ , … , n 1000000007 取模后再写入报表。
形式化地，把周期 d d d H ( d ) H(d) H ( d )
H ( d ) = ( 0 m o d d ) ⋅ v 0 + ( 1 m o d d ) ⋅ v 1 + ⋯ + ( ( n − 1 ) m o d d ) ⋅ v n − 1 . H(d)=(0\bmod d)\cdot v_0+(1\bmod d)\cdot v_1+\cdots+((n-1)\bmod d)\cdot v_{n-1}.
H ( d ) = ( 0 mod d ) ⋅ v 0 + ( 1 mod d ) ⋅ v 1 + ⋯ + (( n − 1 ) mod d ) ⋅ v n − 1 . 请依次给出 H ( ‘ 1 ‘ ) , H ( ‘ 2 ‘ ) , … , H ( n ) H(`1`),H(`2`),\ldots,H(n) H ( ‘1‘ ) , H ( ‘2‘ ) , … , H ( n ) 1000000007 取模后的结果。
约束：
1 ≤ \le ≤ n n n ≤ \le ≤ 2000000 ≤ \le ≤ v i v_i v i ≤ \le ≤ 1000000000
输入描述
第一行一个整数 n n n 1 ≤ \le ≤ n n n ≤ \le ≤ 200000），表示彩灯盏数。
第二行 n n n v 0 , v 1 , … , v n − 1 v_0,v_1,\ldots,v_{n-1} v 0 , v 1 , … , v n − 1 0 ≤ \le ≤ v i v_i v i ≤ \le ≤ 1000000000），表示各盏灯的标定亮度。
输出描述
输出一行 n n n H ( ‘ 1 ‘ ) , H ( ‘ 2 ‘ ) , … , H ( n ) H(`1`),H(`2`),\ldots,H(n) H ( ‘1‘ ) , H ( ‘2‘ ) , … , H ( n ) 1000000007 取模后的值。
样例1
输入
4
3 1 4 2
输出
0 3 9 15
说明
H ( ‘ 1 ‘ ) H(`1`) H ( ‘1‘ ) 1 取余都是 0，总和为 0H ( ‘ 2 ‘ ) H(`2`) H ( ‘2‘ ) ( 0 ⋅ ‘ 3 ‘ ) + ( 1 ⋅ ‘ 1 ‘ ) + ( 0 ⋅ ‘ 4 ‘ ) + ( 1 ⋅ ‘ 2 ‘ ) = ‘ 3 ‘ (0\cdot `3`)+(1\cdot `1`)+(0\cdot `4`)+(1\cdot `2`)=`3` ( 0 ⋅ ‘3‘ ) + ( 1 ⋅ ‘1‘ ) + ( 0 ⋅ ‘4‘ ) + ( 1 ⋅ ‘2‘ ) = ‘3‘ H ( ‘ 3 ‘ ) H(`3`) H ( ‘3‘ ) ( 0 ⋅ ‘ 3 ‘ ) + ( 1 ⋅ ‘ 1 ‘ ) + ( 2 ⋅ ‘ 4 ‘ ) + ( 0 ⋅ ‘ 2 ‘ ) = ‘ 9 ‘ (0\cdot `3`)+(1\cdot `1`)+(2\cdot `4`)+(0\cdot `2`)=`9` ( 0 ⋅ ‘3‘ ) + ( 1 ⋅ ‘1‘ ) + ( 2 ⋅ ‘4‘ ) + ( 0 ⋅ ‘2‘ ) = ‘9‘ H ( ‘ 4 ‘ ) H(`4`) H ( ‘4‘ ) ( 0 ⋅ ‘ 3 ‘ ) + ( 1 ⋅ ‘ 1 ‘ ) + ( 2 ⋅ ‘ 4 ‘ ) + ( 3 ⋅ ‘ 2 ‘ ) = ‘ 15 ‘ (0\cdot `3`)+(1\cdot `1`)+(2\cdot `4`)+(3\cdot `2`)=`15` ( 0 ⋅ ‘3‘ ) + ( 1 ⋅ ‘1‘ ) + ( 2 ⋅ ‘4‘ ) + ( 3 ⋅ ‘2‘ ) = ‘15‘
样例2
输入
1
8
输出
0
说明
只有一盏编号为 0 的灯。H ( ‘ 1 ‘ ) = ( 0 m o d ‘ 1 ‘ ) ⋅ ‘ 8 ‘ = ‘ 0 ‘ H(`1`)=(0\bmod `1`)\cdot `8`=`0` H ( ‘1‘ ) = ( 0 mod ‘1‘ ) ⋅ ‘8‘ = ‘0‘
样例3
输入
6
2 0 5 1 0 3
输出
0 4 16 16 13 28
说明
H ( ‘ 1 ‘ ) H(`1`) H ( ‘1‘ ) 0H ( ‘ 2 ‘ ) H(`2`) H ( ‘2‘ ) 0 , 1 , 0 , 1 , 0 , 1 0,1,0,1,0,1 0 , 1 , 0 , 1 , 0 , 1 0 + 0 + 0 + 1 + 0 + 3 = ‘ 4 ‘ 0+0+0+1+0+3=`4` 0 + 0 + 0 + 1 + 0 + 3 = ‘4‘ H ( ‘ 3 ‘ ) H(`3`) H ( ‘3‘ ) 0 , 1 , 2 , 0 , 1 , 2 0,1,2,0,1,2 0 , 1 , 2 , 0 , 1 , 2 0 + 0 + 10 + 0 + 0 + 6 = ‘ 16 ‘ 0+0+10+0+0+6=`16` 0 + 0 + 10 + 0 + 0 + 6 = ‘16‘ H ( ‘ 4 ‘ ) H(`4`) H ( ‘4‘ ) 0 , 1 , 2 , 3 , 0 , 1 0,1,2,3,0,1 0 , 1 , 2 , 3 , 0 , 1 0 + 0 + 10 + 3 + 0 + 3 = ‘ 16 ‘ 0+0+10+3+0+3=`16` 0 + 0 + 10 + 3 + 0 + 3 = ‘16‘ H ( ‘ 5 ‘ ) H(`5`) H ( ‘5‘ ) 0 , 1 , 2 , 3 , 4 , 0 0,1,2,3,4,0 0 , 1 , 2 , 3 , 4 , 0 0 + 0 + 10 + 3 + 0 + 0 = ‘ 13 ‘ 0+0+10+3+0+0=`13` 0 + 0 + 10 + 3 + 0 + 0 = ‘13‘ H ( ‘ 6 ‘ ) H(`6`) H ( ‘6‘ ) 6，贡献就是 ∑ i ⋅ v i = ‘ 28 ‘ \sum i\cdot v_i=`28` ∑ i ⋅ v i = ‘28‘
