P8763 [蓝桥杯2021]异或变换 题解

· · 题解

看到题面，首先拿几组样例模拟一下。先给出一个模拟结果生成器，可以求出每一次变换后 \tt 01 串的内容。当然你也可以手玩。

对于这个生成器，在对 a_i 进行异或变换的时候，一定注意 i 要倒序循环，这样才能消除 a_i 变换后对 a_{i+1} 的影响。

#include <cstdio>
#include <cstring>
using namespace std;
int n,t,a[100],b[100];
char s[100];
int main () {
    scanf("%d%d%s",&n,&t,s);
    for(int i=0;i<n;++i) a[i+1]=s[i]^48;
    while(t--) {
        for(int i=n;i>1;--i) a[i]^=a[i-1];
        for(int i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
    }
    return 0;
}

我们就拿这个生成器来玩一玩样例。

我们尝试着输入：

5 10
10110

输出结果：

1 1 1 0 1
1 0 0 1 1
1 1 0 1 0
1 0 1 1 1
1 1 1 0 0
1 0 0 1 0
1 1 0 1 1
1 0 1 1 0
1 1 1 0 1
1 0 0 1 1

于是果断判定有循环节。没有循环节 1e18 还做个啥

对循环节的长度下手。再玩几组样例，可以发现循环节的长度是首个 \geqslant n 的 2 方幂。这不大量地玩样例真的发现不了。

注意到 n \leqslant 10^4，那么循环节长度 \leqslant 2^{14} = 16384。因此，我们令 t 对节长取模，然后模拟即可。在极端数据下，该算法会达到 10^8，虽然卡时较紧，但仍可以通过。

```cpp #include <cstdio> #include <cstring> using namespace std; namespace IO { const int SIZE=(1<<21)+1; char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1; #define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*(iS++))):*(iS++)) inline void flush() {fwrite(obuf,1,oS-obuf,stdout);oS=obuf;} inline void pc(char x) {*oS++=x;if(oS==oT)flush();} template<typename Elem> void in(Elem &rdnum) { rdnum=0;char c=gc();Elem rdflag=1; while(c<'0'||c>'9') {if(c=='-')rdflag=-1;c=gc();} while(c>='0'&&c<='9') {rdnum=(rdnum<<1)+(rdnum<<3)+(c^48);c=gc();} rdnum*=rdflag; } template<typename Elem> void wtt(Elem wtnum) {if(wtnum<10){pc(wtnum+'0');return;} wtt(wtnum/10);pc(wtnum%10+'0');} template<typename Elem> void out(Elem wtnum) {if(wtnum<0){pc('-');wtnum=-wtnum;} wtt(wtnum);flush();} } using namespace IO; inline bool isa(int a) {return a=='0'||a=='1';} inline int in_str(char *str) { int len=1;char c; while(!isa(c=gc()));str[0]=c; while(isa(c=gc()))str[len++]=c; str[len]=0;return len; } int n; long long t; char s[10010]; int main () { in(n),in(t),in_str(s); int a[10010]; for(register int i=0;i<n;++i) a[i+1]=s[i]^48; int len=1; while(len<=n) len<<=1; t%=len; while(t--) { register int i; for(i=n;i>9;i-=8) { a[i]^=a[i-1]; a[i-1]^=a[i-2]; a[i-2]^=a[i-3]; a[i-3]^=a[i-4]; a[i-4]^=a[i-5]; a[i-5]^=a[i-6]; a[i-6]^=a[i-7]; a[i-7]^=a[i-8]; } while(i>1) a[i]^=a[i-1],--i; } for(register int i=1;i<=n;++i) out(a[i]); return 0; } ```