5628：Clarke and math

题目描述

Clarke is a patient with multiple personality disorder. One day, he turned into a mathematician, did a research on interesting things.
Suddenly he found a interesting formula. Given $f(i), 1 \le i \le n$, calculate
$\displaystyle g(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_k \mid i_{k-1}} f(i_k) \text{ mod } 1000000007 \quad (1 \le i \le n)$

输入解释

The first line contains an integer $T(1 \le T \le 5)$, the number of test cases.
For each test case, the first line contains two integers $n, k(1 \le n, k \le 100000)$.
The second line contains $n$ integers, the $i$th integer denotes $f(i), 0 \le f(i) < 10^9+7$.

输出解释

For each test case, print a line contained $n$ integers, the $i$th integer represents $g(i)$.

输入样例

2
6 2
2 3 3 3 3 3
23 3
2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

输出样例

2 7 7 15 7 23
2 9 9 24 9 39 9 50 24 39 9 102 9 39 39 90 9 102 9 102 39 39 9

提示

In the first sample case:
f(1)=2,f(2)=f(3)=f(4)=f(5)=f(6)=3
when k=1
g(1)=f(1)=2,g(2)=f(1)+f(2)=5,g(3)=f(1)+f(3)=5,g(4)=f(1)+f(2)+f(4)=2+3+3=8,g(5)=f(1)+f(5)=5,g(6)=f(1)+f(2)+f(3)+f(6)=2+3+3+3=10
when k=2
g(1)=f(1)=2,g(2)=f(1)+(f(1)+f(2))=7,g(3)=f(1)+(f(1)+f(3))=7,g(4)=f(1)+(f(1)+f(2))+(f(1)+f(4))=15,g(5)=f(1)+(f(1)+f(5))=7,g(6)=f(1)+(f(1)+f(2))+(f(1)+f(3))+(f(1)+f(2)+f(3)+f(6))=23
Therefore output
2 7 7 15 7 23

来自杭电HDUOJ的附加信息

Recommend

hujie

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 BestCoder Round #72 (div.2)

源链接： HDU-5628

最后修改于 2020-10-25T23:24:19+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
5000/2500MS(Java/Others)	65536/65536K(Java/Others)