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 们的代码怎么那么像呢？

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,n2,t,a[200005],b[200005],st[70],top;
inline LL lowbit(LL x){return x&-x;}
int main()
{
    scanf("%lld%lld",&n,&t),n2=(n<<1);
    for(LL i=1;i<=n2;i+=2)scanf("%lld",&a[i]);
    while(t)st[++top]=lowbit(t),t-=st[top];
    while(top)
    {
        LL x=st[top],i,l,r;
        for(t-=x,memset(b,0,sizeof(b)),i=x==1?2:1,x%=n2;i<=n2;i+=2)
            l=((i-x-1+n2)%n2)+1,r=((i+x-1+n2)%n2)+1,b[i]=a[l]==a[r]?1:2;
        swap(a,b),top--;
    }
    for(LL i=1;i<n2;i++)printf("%lld ",a[i]);printf("%lld",a[n2]);
    return 0;
}