【题解】P8763 [蓝桥杯 2021 国 ABC] 异或变换

jifbt · 2022-12-22 20:19:34 · 题解

记 s_{ji} 为第 j 次变换后的串，定义超出范围的值为 0。我们可以注意到一个性质：

进行 2^k 次变换相当于进行两遍 2^{k-1} 次变换，因此用数学归纳法可以证明上式。这里不再赘述。

然后就可以对于每一位来计算。考虑到 t>n 时实际上没有进行变换，时间复杂度约为 O(n \log \min(n, t))。

#include<bits/stdc++.h>
using namespace std;
template<typename T>void rd(T&x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
    x*=f;
}
typedef long long ll;
const int N=1e4+10;
int n;
ll t;
bool a[N];
int main(){
    rd(n);rd(t);
    for(int i=0;i<n;++i)a[i]=getchar()&1;
    while(t){
        ll l=t&-t;t-=l;
        for(int i=n-1;i>=l;--i)a[i]^=a[i-l];
    }
    for(int i=0;i<n;++i)putchar(a[i]^48);
}