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;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *