1

以下是来自Interviewstreet的问题,有人可以给我一些测试用例以及输出。我的解决方案在所有测试用例的时间限制内,但给出了错误的答案。

圆求和(30 分)

孩子们N围成一圈坐着,1,2,...,N顺时针编号。ith孩子有一张纸,上面ai写着数字。他们玩以下游戏:

在第一轮中,被编号的孩子x将他的邻居的数字加到他的数字上。

在第二轮中,顺时针顺序的下一个孩子将他的邻居的数字之和加到他的数字上,依此类推。

比赛在M回合结束后结束。

输入:第一行包含T,测试用例的数量。T案例如下。测试用例的第一行包含两个空格分隔的整数NM. 下一行包含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 
4

1 回答 1

1

如果它似乎对小型测试用例没问题,但不是全部,我猜你有溢出问题。

确保你要么...

  • 每次相加后做模数,而不仅仅是在三个数字相加之后。
  • 使用 64 位数字。这仍然需要模数,但不那么频繁。

1000000007 非常接近有符号 32 位数字 (214748367) 的限制。您可以添加到调制数字而不会溢出,但不能添加三个。

于 2012-05-20T13:46:10.923 回答