Circle Summation（30分）InterviewStree益智

Question

以下是Interviewstreet的問題我沒有從他們的網站獲得任何幫助，所以在這裏提問。我對算法/解決方案不感興趣，但我不理解他們給出的解決方案作爲他們第二個輸入的例子。任何人都可以幫助我理解問題陳述中指定的第二個輸入和輸出。

圈總和（30分）

有N孩子沿着圓圈坐着，編號順時針1,2,...,N。 ith孩子的一張紙上寫着一個號碼ai。他們玩下面的遊戲：

在第一輪中，編號爲x的孩子在他的數字中增加了他的鄰居的數量總和。

在第二輪中，順時針順序的下一個孩子將其鄰居的數量總和加到他的數字上，依此類推。

遊戲結束後M已發揮。

輸入： 第一行包含T，測試用例的數量。 T個案如下。測試用例的第一行包含兩個空間分離的整數N和M。下一行包含N整數，ith號碼爲ai。

輸出： 對於每個測試案例，輸出N行，每行有N個整數。 ith行上的jth整數包含第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，孩子2有數字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，4）→（* 7,2,4）→（7，* 13,4）→（7,13，* 24） ）

而且正如您注意到第二種情況的輸出正好是以這種方式計算的三個三元組。

希望有所幫助。