426. Box-ball system http://projecteuler.net/problem=426 有一排无限多的箱子，并在其中一部分的箱子里放了一颗球。 举例来说，如果我们由左至右有两个箱子有球、两个空箱、两个箱子有球、一个空箱、 两个箱子有球，其余均为空箱，则我们记作(2, 2, 2, 1, 2)，依序代表有球和没球的 箱子个数。 定义一回合的行动为依序对每颗球进行一次如下动作：把最左边没动过的球移到其右边 最接近的空箱。 在经过一回合的行动後，(2, 2, 2, 1, 2)会变成(2, 2, 1, 2, 3)，如下图所示；注意 到所有的状态表示永远都是从第一个有球的箱子开始计算。 http://projecteuler.net/project/images/p_426_baxball1.gif 上述系统一般称之为箱球系统（Box-Ball System），或简写为BBS。 可以证明在经过足够多回合的行动後，此系统会演变成一稳定状态，使得每个接连有球 的箱子数不会再改变。在下面这个例子中，接连有球的的箱子数最终演变为[1, 2, 3]； 我们把这种状态称为其终态。 http://projecteuler.net/project/images/p_426_baxball2.gif 我们定义一数列{t_i}如下： 　‧s_0 = 290797 　‧s_(k+1) = s_k^2 mod 50515093 　‧t_k = (s_k mod 64) + 1 如果由初始状态(t_0, t_1, ..., t_10)开始行动，则其终态为[1, 3, 10, 24, 51, 75]。 试求由初始状态(t_0, t_1, ..., t_10000000)开始行动的终态。 请给出每个终态元素的平方和作为最终答案。例如如果终态是[1, 2, 3]，则答案为 1^2 + 2^2 + 3^2 = 14。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 129.2.129.163 ※ 编辑: tml 来自: 129.2.129.163 (05/05 15:56)