算法拼图的测试用例

以下是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，你不会有这个问题。 –

算法拼图的测试用例

回答

相关问题