Відновіть масив (Розбір)

Рішення

Ми можемо скасувати процес префіксної суми, щоб отримати оригінальний масив, це можна зробити за допомогою масиву різниць, тому новий зворотний процес буде:

• розгляньте початковий елемент x=a_1.

• a_1 залишається незмінним.

• розгляньте масив різниць $d$ з d_1,d_2,..,d_{n-1}

• пройдіть через всі i=2,..,n, тоді d_i \gets a_i-a_{i-1}

• a \gets [a_1,d_1,d_2,..,d_{n-1}]

Процес буде повторюватися точно $k$ разів, і тоді оригінальний масив $a$ буде відновлено.

Складність $O(nk)$

def solve():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    for _ in range(k):
        d=[]
        for i in range(1,n):
            d.append(a[i]-a[i-1])
        a=[a[0]]+d
    print(*a)

for _ in range(int(input())):
    solve()