Суммирование кругов (30 баллов)

Question

Следующая проблема - от Interviewstreet Я не получаю никакой помощи от их сайта, поэтому задаю вопрос здесь. Я не заинтересован в алгоритме / решении, но я не понял решение, данное ими в качестве примера для их второго ввода. Кто-нибудь, пожалуйста, помогите мне понять второй вход и выход, как указано в постановке задачи.

Круг суммирования (30 баллов)

По кругу сидят N дети, пронумерованные 1,2,...,N по часовой стрелке. У ребенка ith есть лист бумаги с номером ai, написанным на нем. Они играют в следующую игру:

В первом раунде ребенок с номером x добавляет к своему числу сумму чисел своих соседей.

Во втором раунде следующий по часовой стрелке ребенок добавляет к своему числу сумму чисел своих соседей и т. Д.

Игра заканчивается после M раундов.

Входной сигнал: Первая строка содержит T, количество тестов. T случаев следуют. Первая строка для теста содержит два целых числа, разделенных пробелами N и M. Следующая строка содержит N целых чисел, число ith равно ai.

Выход: Для каждого теста выведите N строк, каждая из которых имеет N целых чисел. Целое число jth в строке ith содержит число, которым заканчивается j-й ребенок, если игра начинается с ребенка i, играющего в первом раунде. Выведите пустую строку после каждого теста, кроме последнего. Поскольку числа могут быть действительно огромными, выведите их по модулю 1000000007.

Ограничения:

1 <= T <= 15
3 <= N <= 50
1 <= M <= 10^9
1 <= ai <= 10^9

Пример ввода:

2
5 1
10 20 30 40 50
3 4
1 2 1

Пример вывода:

80 20 30 40 50
10 60 30 40 50
10 20 90 40 50
10 20 30 120 50
10 20 30 40 100



23 7 12
11 21 6
7 13 24 

Answer 1

Вот объяснение второго контрольного примера.Я буду использовать обозначение (a, b, c), означающее, что ребенок один имеет номер a, ребенок два имеет номер b, а ребенок три имеет номер c.В начале позиция всегда (1,2,1).

Если первый ребенок первым суммирует своих соседей, таблица проходит через следующие ситуации (я поставлю звездочку передребенок, который только что добавил свои два соседних номера):

(1,2,1) -> (* 4,2,1) -> (4, * 7,1) -> (4,7, * 12) -> (* 23,7,12)

Если второй ребенок перемещается первым:

(1,2,1) -> (1, * 4, 1) -> (1,4, * 6) -> (* 11,4,6) -> (11, * 21,6)

И последний, если третий ребенок двигается первым:

(1,2,1) -> (1,2, * 4) -> (* 7,2,4) -> (7, * 13,4) -> (7,13,* 24)

И, как вы заметили, во втором случае вычисляются именно три тройки.

Надеюсь, это поможет.