设m时刻的状态为tm,tm为一个数列，每个数字表示该位置上的灯的状态变换次数。则tm=tm-1 + f(tm-1)，不进位

f(t)表示将t的第1位换到第1位，……第n位换到地1位，

由递推可得通项：tm=sigma C(m,k)*fk(t0) ,(k=0 to m) ,fk(t0)表示f(t0)迭代k次

设，Sn=tn mod 2，则Sn所表示的01串即为时刻n的状态。

观察杨辉三角可得规律：2^p+1行（即(x+y)^p的展开式系数）只有首尾为奇数，因此题目中只要m=2^p，则可以快速求出，若m2^p，将m分解成2的幂之和后依次求。

【问题分析】

直接模拟，必然超时。考虑到时刻m最大达到109，而它的二进制表示最多只有30位。如果我们能够找到与例一相似的方法，计算时刻m时，只算log(m)次，则n个灯泡，只计算nlog(m)，最多约3000万次，就能在1秒的时限内出解了。

1．找规律

我们从简单的情况入手，找规律。

在时刻t时，以X[k]=1表示第k个灯是亮的，以X[k]=0表示第k个灯为暗的。如果时刻t时各灯状态分别为X[1]，X[2]，…，X[n]，则时刻t+1时各灯状态为：X[1] xor X[n]，X[2] xor X[1]，X[3] xor X[2]，…，X[n] xor X[n-1]。

时刻0 时刻1 时刻2 时刻3 时刻4 时刻5 时刻6 时刻7 时刻8 时刻9 时刻10 时刻11 时刻12 时刻13 时刻14 时刻15 时刻16

灯1 1 15 14 1345 12 25 1245 23 13 1235 34 24 1234 45 35 2345 15

灯2 2 12 25 1245 23 13 1235 34 24 1234 45 35 2345 15 14 1345 12

灯3 3 23 13 1235 34 24 1234 45 35 2345 15 14 1345 12 25 1245 23

灯4 4 34 24 1234 45 35 2345 15 14 1345 12 25 1245 23 13 1235 34

灯5 5 45 35 2345 15 14 1345 12 25 1245 23 13 1235 34 24 1234 45

以n=5为例，当时刻0时，灯k的状态以X[k]表示（为1表示亮，为0表示暗）。在上表中，简单地以数字k代表X[k]。则：

（1）时刻1时

灯1状态为：时刻0时灯5 状态xor 时刻0时灯1 状态，即X[5] xor X[1]；表格中，简记为15。

灯2状态为：时刻0时灯1 状态xor 时刻0时灯2 状态，即X[1] xor X[2]；表格中，简记为12。

灯3状态为：时刻0时灯2 状态xor 时刻0时灯3 状态，即X[2] xor X[3]；表格中，简记为23。

灯4状态为：时刻0时灯3 状态xor 时刻0时灯4 状态，即X[3] xor X[4]；表格中，简记为34。

灯5状态为：时刻0时灯4 状态xor 时刻0时灯5 状态，即X[4] xor X[5]；表格中，简记为45。

（2）时刻2时

灯1状态为：时刻1时灯5 状态xor 时刻1时灯1 状态，即：

（X[4] xor X[5]）xor（X[5] xor X[1]）=X[1] xor X[4]；表格中，简记为14。

灯2状态为：时刻1时灯1 状态xor 时刻1时灯2 状态，即：

（X[5] xor X[1]）xor（X[1] xor X[2]）=X[5] xor X[2]；表格中，简记为25。

灯3状态为：时刻1时灯2 状态xor 时刻1时灯3 状态，即：

（X[1] xor X[2]）xor（X[2] xor X[3]）=X[1] xor X[3]；表格中，简记为13。

灯4状态为：时刻1时灯3 状态xor 时刻1时灯4 状态，即：

（X[2] xor X[3]）xor（X[3] xor X[4]）=X[2] xor X[4]；表格中，简记为24。

灯5状态为：时刻1时灯4 状态xor 时刻1时灯5 状态，即：

（X[3] xor X[4]）xor（X[4] xor X[5]）=X[3] xor X[5]；表格中，简记为35。

（3）其余时刻各盏灯的状态，也可以使用相同的方法求得。

观察该表，发现规律：

如果t时刻第p个灯状态为Y[p]，则t+2k时刻第p个灯泡状态为：t时刻第p个灯的状态 xor t时刻p朝左数2k个灯的状态。即Y[p] xor Y[(p-2k-1)mod n+1]。

比如，我们求时刻13时各盏灯的状态，可以按以下的步骤求：

①由时刻0各盏灯的状态，求得时刻1时各盏灯的状态；

②由时刻1各盏灯的状态，求得时刻5时各盏灯的状态；

③由时刻5各盏灯的状态，求得时刻13时各盏灯的状态；

一般地，因为时刻m可以表示为二进制数brbr-1…b2b1，而其中的某位bk表示bk*2k-1(bk=1或0)。如果上述规律是正确的，则可以由时刻0的n个灯状态推得时刻b1*20的n个灯状态，由时刻b1*20推得时刻b2*21+b1*20的n个灯状态，由时刻b2*21+b1*20的n个灯状态推得时刻b3*22+b2*21+b1*20的n个灯状态，…，最后由时刻br-1*2r-2+…+b2*21+b1*20的n个灯状态推得时刻br*2r-1+…+b2*21+b1*20的n个灯状态。问题可以在O(nlog(m))的时间复杂度下解决。

2．规律的证明

下面采用数学归纳法进行证明。

（1）当k=0时，2k=1，结论就是问题的定义，显然成立。

（2）假设当k=r-1（r≥1）时，结论成立。

如果时刻t时，第p个灯为Y[p]，第p左数2r-1个灯为Y[(p-2r-1-1) mod n+1]，第p左数2r个灯(即第p左数2r-1个后再左数2r-1个)为Y[(p-2r-1) mod n+1]。

①时刻t+2r-1时灯p状态为：时刻t时灯p的状态 xor 时刻t时灯p左数2r-1个灯的状态，即Y[p] xor Y[(p-2r-1-1) mod n+1]

②时刻t+2r-1时灯p左数2r-1个灯的状态为：时刻t时灯p左数2r-1个灯的状态 xor 时刻t时灯p左数2r个灯的状态，即Y[(p-2r-1-1) mod n+1] xor Y[(p-2r-1) mod n+1]

当时刻(t+2r-1)+2r-1时，灯p的状态为：时刻(t+2r-1)时灯p的状态 xor时刻(t+2r-1)时灯p左数2r-1个灯的状态，即：

(Y[p] xor Y[(p-2r-1-1) mod n+1]) xor (Y[(p-2r-1-1) mod n+1] xor Y[(p-2r-1) mod n+1])

= Y[p] xor Y[(p-2r-1) mod n+1]

即当k=r时，结论也成立！

由(1)和(2)知，对于任意大于等于0的整数k， 如果时刻t时灯p的状态为Y[p]，则时刻t+2k时，灯p的状态为Y[p] xor Y[(p-2k-1) mod n+1]。

证毕！

于是，可以将m分解为二进制表示，对于二进制对应的非0的第k位，如果原来第p（1≤p≤n）个灯状态为X[p]，则时刻加上该位表示的值后，第p个灯状态为X[p] xor X[(p-2k-1-1) mod n+1]。

为节约空间，可以采用滚动数组来存储每个时刻各盏灯的状态。

【算法】

1、求得m的二进制表示：f[r..1]

2、根据输入数据得到n个灯泡的初始状态x[0,1],x[0,2],x[0,3],…,x[0,n]

其中灯亮的取值1,不亮取值0;

3、C←0;//滚动数组，初始第0行

4、For k←1 to r do //扫描m的二进制各位

5、 if f[k]=1 then begin

6、 C←1-c;

7、 For j←1 to n do

8、 x[c,j]←x[1-c,j] xor x[1-c,((j-2k-1-1) mod n+n)mod n+1];

end

9、输出最终n个灯的状态:x[c,1],x[c,2],x[c,3],…,x[c,n]

《转》

直接模拟，必然超时。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...