环形序列
  • 板块学术版
  • 楼主SulphurDXD
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/22 11:35
  • 上次更新2024/11/22 16:19:37
查看原帖
环形序列
527674
SulphurDXD楼主2024/11/22 11:35

给定一个长度为 nn 的自然数序列 a=[a0,a1,,an1]a = [a_0, a_1, \ldots, a_{n - 1}],每次操作同时对序列的每个位置 ii0i<n0 \le i < n)令 aiaiai1aiai+1a_i \larr |a_i - a_{i - 1}| \oplus |a_i - a_{i + 1}|,下标默认模 nn

暴力测试:

#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;
}

这个序列是否会在有限步数内进入一个循环,如果是,这个步数的规模是怎样的?有什么快速求出 kk 步后序列的算法?它还有什么其他性质吗?

2024/11/22 11:35
加载中...