模拟稳超时...

...........................

和2^k有关的数学方法

Accepted 有效得分：100 有效耗时：405ms

悲剧了，字符一开始打错了=.=

为什么我的速度这么慢……（好像数组开太大了……）

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 25ms

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

├ 测试数据 08：答案正确... 87ms

├ 测试数据 09：答案正确... 40ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：217ms

一次AC

编译通过...

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

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

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

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

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

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 88ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：314ms

我和4楼的一样：

编译通过...

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

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

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

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

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

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

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

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

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

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

反正结论就是：

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

还有，题目描述有误，实际的数据范围应为：

100%的数据，1≤n≤1000000

这题本质和P1554硬币游戏一样。

第一次格式错误，第二次同样的程序却秒杀，这是为什么

好题啊，没想到

好题目！

为什么我想不到呢。。。郁闷。。。

sdfghsfghjdgh

那个规律很有意思.

注意滚动数组别滚错了- -

AC了.

其实就是找规律,将m分解为2的幂的和(x1,x2,x3,x4..xt),

然后每个时刻j的的每个灯泡状态Ai就是上一个时刻的灯泡状态Bi xor B[(i+xj) mod n].

可以用滚动数组来节省空间.

vikeydr转的那个证明太强了OrzOrz

while m0 do begin p:=c; c:=not c; k:=m and -m; m:=m xor k; for i:=0 to n-1 do f[c,(i+k) mod n]:=f[p,i] xor f[p,(i+k) mod n];end;

Who can give me this key?

i can't ac.

thanks!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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

( 2007-7-31 18:43:54 )

爽哉

你们大家都把Dennis用来投稿赚钱的文章给贴出来了都

看着晕啊．．