算法拼圖的測試用例

以下是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

來源

2012-05-20 user1301541

如果它似乎對小測試的情況下做的好，但不是全部，我會猜測你有溢出問題。

確保你要麼...

執行模每次加入後，不僅將所有三個數字後。
使用64位數字。這仍然需要模數，但並不經常。

1000000007非常接近有符號32位數字（214748367）的限制。您可以添加到調製數字而不會溢出，但不能添加三個。

來源

2012-05-20 13:46:10

你假設ai = 10^9和m = 10^9，n太小，這意味着最後ai約爲10^18。和64位數是足夠的，因爲64位符號數等於2^63 = 8 *（2^10）^ 6 = 8 * 10^18 –

最大可能的總和：1000000006 + 1000000006 + 1000000006 = 3000000018> 2147483647 = 2^31 - 1（帶符號32位數字的最大值），這意味着它將環繞到-1294967278。如果你反而（（1000000006 + 1000000006）％1000000007 + 1000000006）％1000000007，你不會有這個問題。 –

算法拼圖的測試用例

回答

相關問題