专栏文章

题解：CF2071D1 Infinite Sequence (Easy Version)

MMeickol
CF2071D1题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minygg9b
此快照首次捕获于
2025/12/02 10:24
3 个月前
此快照最后确认于
2025/12/02 10:24
3 个月前
查看原文

异或前缀和 + 性质挖掘 + 递归

设 ss 数组为 aa 数组的异或前缀和，即 si=⊕k=1iaks_i=\oplus_{k=1}^i a_k。
显然当 m≤nm \le n 时直接输出 aia_i 即可。所以本题难点自然是在于 m>nm \gt n 的部分如何求。
由题意当 m>nm \gt n 时，am=s⌊m2⌋\large a_m=s_{\lfloor \frac{m}{2} \rfloor}。
当 ii 为奇数时：显然 ⌊i2⌋=⌊i−12⌋\lfloor \frac{i}{2} \rfloor= \lfloor \frac{i-1}{2} \rfloor，又当 m>nm \gt n 时 am=s⌊m2⌋\large a_m=s_{\lfloor \frac{m}{2} \rfloor}，故当 i−1>ni-1 \gt n 且 ii 为奇数时有 ai=ai−1a_{i}=a_{i-1}。
根据 ss 数组的递推定义：si=si−1⊕ais_i=s_{i-1} \oplus a_i。结合刚刚分析的性质，当 ii 为奇数且 i−1>ni-1 \gt n 时：有 ai=ai−1a_i=a_{i-1}，为了用上这个条件于是将 si=si−1⊕ais_i=s_{i-1} \oplus a_i 转化为 si=si−2⊕ai−1⊕ais_i=s_{i-2} \oplus a_{i-1} \oplus a_i，而 ai−1=aia_{i-1}=a_i，故 si=si−2s_i=s_{i-2}。
即对于所有 ≥n\ge n 的奇数项都相等。（因为当 nn 为偶数时，sn+1,sn+2,…s_{n+1},s_{n+2},\dots 均相等；当 nn 为奇数时，sn,sn+1,⋯s_n,s_{n+1},\cdots 均相等。）
接着考虑当 i>ni \gt n 且 ii 为偶数时：si=si−1⊕ais_{i}=s_{i-1} \oplus a_i，因为 i>ni \gt n，故 si=si−1⊕s⌊m2⌋s_i=s_{i-1} \oplus s_{\lfloor \frac{m}{2} \rfloor}，其中 si−1s_{i-1} 是确定的值，就等于第一个 ≥n\ge n 的奇数项对应的值，而 s⌊m2⌋s_{\lfloor \frac{m}{2} \rfloor} 则可继续递归得到，显然递归层数最多也只有 log⁡\log 层。
时间复杂度 O(n+log⁡l)O(n +\log l)。
CPP
#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int N=2e5+5;
LL n,l,r;
int a[N];
LL prexor[N];
LL dfs(LL now){ // 递归首层求>n的now对应的值a[now],由于a[now]=prexor[now/2],进而不断递归求解
	if(now<=n) return prexor[now];
	else if(now/2<=n) return dfs(now/2);
	now/=2;
	LL odd;
	if(n&1) odd=prexor[n];
	else odd=prexor[n]^dfs(n+1);
	if(now&1) return odd;
	else return odd^dfs(now);
}
void solve(){
	cin>>n>>l>>r;
	rep(i,1,n) cin>>a[i];
	rep(i,1,n) prexor[i]=prexor[i-1]^a[i];
	if(l<=n) return cout<<a[l],void();
	cout<<dfs(l);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...