周赛 134第2题
预备知识
只有a⊕a=0和(a⊕b)⊕(c⊕d)=a⊕b⊕c⊕d和a⊕0=a
请看下图:
这是i mod 1,i mod 2,i mod 3……i mod n时的结果
可以发现i mod x(x>i)时结果一定为i(废话),但它们对答案没有贡献吗?其实有些是有的。
而剩下的竖着看发现是(0),(0,1),(0,1,2)……的规律
我们先计算(imod1)⊕(imod2)⊕…⊕(imodn) 这一部分再计算ai⊕(ai+1)⊕……这一部分
所以就有了第一阶段的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,ans=0;
scanf("%d",&n);
int s=n%2?2:1;//n和i不同奇偶时mod x(x>i)时才影响答案,因为这是后面的数的个数才是奇数,可看上方的图
for(;s<n;s+=2)ans^=s;//处理i mod x(x>i)时会影响答案的数
for(int i=2;i<=n;i++){//枚举竖列,判断按(0,1,2,3……)的规律有几组
int j=n-i+1;//这一竖列有n-i+1个数
if(j%i==0&&j/i%2==0)continue;//刚好分完,且分成偶数组,跳过(因为异或两两抵消)
for(int k=1;k<j%i;k++)ans^=k;//没刚好分完,算剩下的
if(j/i%2)for(int k=1;k<=i-1;k++)ans^=k;//奇数组就再算一组
}
for(int i=1;i<=n;i++){//算a[1~n]
int x;
scanf("%d",&x);
ans^=x;
}
cout<<ans;
return 0;
}
时间复杂度 O(n^2)无法AC
我们可以发现可一预处理(0⊕1),(0⊕1⊕2)……的结果
时间复杂度 O(n)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int b[1000005];
int main(){
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)b[i]=b[i-1]^i;//预处理
int s=n%2?2:1;
for(;s<n;s+=2)ans^=s;
for(int i=2;i<=n;i++){
int j=n-i+1;
if(j%i==0&&j/i%2==0)continue;
ans^=b[j%i-1];//被省了
if(j/i%2)ans^=b[i-1];//被省了
}
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
ans^=x;
}
cout<<ans;
return 0;
}
写的不好,请见谅