|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1.5 초||1024 MB||1||1||1||100.000%|
The memory of Bob’s computer contains two interesting things: an array of integers and a virus.
Each midnight the virus becomes active. It takes each array in memory and replaces it with a bunch of new arrays: one for each contiguous subarray of the original array.
For example, if today the memory contains a single array (1,2,1,3), tomorrow it will contain the following arrays: (1), (2), (1), (3), (1,2), (2,1), (1,3), (1,2,1), (2,1,3), and (1,2,1,3).
You are given the length N of Bob’s original array, its contents and the number of days D.
Compute the sum of all elements of all arrays that will be in the memory of Bob’s computer after D days. As this number can be huge, it is sufficient to compute the remainder it gives when divided by 109 + 9.
Assume that the memory of Bob’s computer is sufficiently large to accommodate all the arrays.
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of two lines. The first line contains the two integers N and D. The second line consists of N non-negative integers that are all less than 100,000: the contents of the original array.
You may assume that N ≤ 100,000 and D ≤ 100,000.
For each test case output a single line with a single integer: the sum of all elements in all arrays after D days, modulo 1,000,000,009.
3 4 1 1 2 1 3 1 10 47 2 10 1 2
34 47 33
You can test it on the following input: N = D = 100000, array = (1,2,3,…,99999,100000). The correct output is 92629705.
Contest > Internet Problem Solving Contest > IPSC 2010 Q번 (수정)