Hi guys , i'm solving this problem:
For array a[i] with n elements ( 1 <= n <= 3000 , abs(a[i]) <= 10^9 )
Ask: After m loop ( 1 <= m <= 10^9 ) , print all of value in array a. Every loop , a[i]=a[i] + a[i-1] + ... + a[1]
Test input: 5 4 2 8 1 1 2
Test output: 4 10 24 39 55
Explain: loop1: 4 6 14 15 16 loop2: 4 10 24 39 55
My ideas was found formula math
I detects this:
For ex with n=5 , m=5 , in array a[5] , we have: loop1: a5 + a4 + a3 + a2 + a1
loop2: a5 + 2a4 + 3a3 + 4a2 + 5a1
loop3: a5 + 3a4 + 6a3 + 10a2 + 15a1
loop4: a5 + 4a4 + 10a3 + 20a2 + 35a1
loop5: a5 + 5a4 + 15a3 + 35a2 + 70a1
Look at this matrix , we are only care about the coefficent , so we have:
1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
1 5 15 35 70
So the intiall problem change to the problem how to calcute quickly for function f(i)(j) , with:
f(1)(j) = 1 , f(i)(1) = 1
f(i)(j) = f(i-1)(j) + f(i)(j-1)
I can't find the formular for this function , so i need anybody helps me to find the formular or solve the intiall problem.
Thank you so much !