简单题。CF 评分才 *1600。
可以直接先把 \(Q\) 拆成两部分。
\[\begin{aligned} \large a&=\oplus^n_{i=1}p_i\\ \large b&=\oplus^n_{i=1}\oplus^n_{j=1}\ \ \ (i\bmod j)\\ \large Q&=a\oplus b \end{aligned} \]\(a\) 很好算，我们看一下 \(b\) 具体要怎么算。
把 \(b\) 所有项写出来：
\[\begin{aligned} b=&(1\bmod 1)\oplus(1\bmod 2)\oplus...(1\bmod n)\oplus\\ &(2\bmod 1)\oplus(2\bmod 2)\oplus...(2\bmod n)\oplus\\ &...\\ &(n\bmod 1)\oplus(n\bmod 2)\oplus...(n\bmod n)\\ =&(1\bmod 1)\oplus(2\bmod 1)\oplus...(n\bmod 1)\oplus\\ &(1\bmod 2)\oplus(2\bmod 2)\oplus...(n\bmod 2)\oplus\\ &...\\ &(1\bmod n)\oplus(2\bmod n)\oplus...(n\bmod n)\\ \end{aligned} \]发现 \(i\) 和 \(j\) 的位置互换并不会有什么影响。
所以我们有：
\[\large b=\oplus^n_{i=1}\oplus^n_{j=1}\ \ \ (i\bmod j)=\oplus^n_{i=1}\oplus^n_{j=1}\ \ \ (j\bmod i) \]记 \(\large pre_i=\oplus^i_{s=1}s\)，根据异或的性质，我们有 \(a\oplus a=0\)。
那么
\[\oplus^n_{j=1}\ \ \ (j\bmod i)= \left\{ \begin{aligned} pre_{n\bmod i}\ \ \ \ \ \ \ \lfloor \frac{n}{i}\rfloor\bmod 2=0\\ pre_{n\bmod i}\oplus pre_i\ \ \ \ \ \ \ \lfloor \frac{n}{i}\rfloor\mod2=1 \end{aligned} \right. \]则
\[\begin{aligned} \large b&=\oplus^n_{i=1}\oplus^n_{j=1}\ \ \ (j\bmod i)\\ \large &=pre_{n\bmod i}\oplus^n_{i=1\&\lfloor \frac{n}{i}\rfloor\bmod 2=1}\ pre_i \end{aligned} \]那么代码就很好写了。
#include<cstdio>
#define ll long long
const int N=1e6+10;
int n;
ll pre[N],ans;
ll p;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&p),ans^=p,pre[i]=pre[i-1]^i;
for(int i=1;i<=n;i++)
{
if((n/i)&1) ans^=pre[i-1];
ans^=pre[n%i];
}
printf("%lld",ans);
return 0;
}
时间复杂度 \(O(n)\)。
标签：pre,...,题解,bmod,large,CF424C,oplus,aligned From： https://www.cnblogs.com/osfly/p/17774224.html