1. 题目

传送门= ̄ω ̄=

2. 题解

数学归纳法
什么鬼?其实就是找规律……
考试找了两个小时没找到规律然后就爆炸了
不难发现当前状态进行$2^k$次操作后,第i位上的数字只受第$i-2^k$位上的数字和第$i+2^k$位上的数字,即它们如果相同则第i位上的数字为1,否则为2。
于是乎,我们就可以做出这题了。

二进制拆分t,用lowbit就行了,总复杂度$O(nlogt)$

当然我还要引用一段证明:

我们可以把每两次操作看成是一次操作,那么每经过一次操作后所有的硬币的位置都不会变化。很容易可以得知每一次操作时的第i个硬币是由上一次操作后的第i+1个硬币和第i-1个硬币异或而来。那么现在我们来求证在第2^k次操作时硬币i由初始状态的第i+2^k和第i-2^k个硬币异或而来。首先当k=0时是满足条件的,那么我们假设当k=n时满足条件,则当k=n+1时每一个硬币i由经过2^n次操作后的状态的第i+2^n和第i-2^n个硬币异或而来,设这两个硬币为x1和x2,那么x1就是由初始状态的第i和第i+2^(n+1)个硬币异或而来,x2是由初始状态的第i和第i-2(n+1)个硬币异或而来,那么很容易发现第i个硬币被抵消掉了,那么当k=n+1时第i个硬币就由初始状态下的第i+2^(n+1)和i-2^(n+1)个硬币得到。

但是对于$2^0=1$我们得特殊处理,我懒得写那么长的代码,搞个栈从大到小搞就行了。

还有,bzoj上不能输出多余空格,不然会PE

顺便吐槽一下:网上那些dalao们的代码怎么那么像呢?

代码: