给定一个长度为 n 的自然数序列 a=[a0,a1,…,an−1],每次操作同时对序列的每个位置 i(0≤i<n)令 ai←∣ai−ai−1∣⊕∣ai−ai+1∣,下标默认模 n。
暴力测试:
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=0; bool f=1; char c=getchar();
while(c<48||c>57) f^=(c==45), c=getchar();
while(c>=48&&c<=57) x=x*10+(c&15), c=getchar();
return f?x:-x;
}
const int N=200105;
int n, a[N], b[N];
int main(){
n=read();
for(int i=0; i<n; i++) a[i]=read();
while(1){
for(int i=0; i<n; i++) b[i]=abs(a[i]-a[(i+n-1)%n])^abs(a[i]-a[(i+1)%n]);
for(int i=0; i<n; i++) a[i]=b[i], printf("%d%c", a[i], " \n"[i==n-1]);
system("pause >nul"); // 按任意键显示下一行
}
return 0;
}
这个序列是否会在有限步数内进入一个循环,如果是,这个步数的规模是怎样的?有什么快速求出 k 步后序列的算法?它还有什么其他性质吗?