C++ 解法, 执行用时: 91ms, 内存消耗: 5240K, 提交时间: 2022-04-25 10:08:54

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int ll
#define ll long long
const int maxn=5e6+5;
int cnt;
int a[maxn],ans[maxn],in[maxn];
int n,c; 
signed main(){
	cin>>n>>c;
	if(c==1){
		for(int i=1;i<=n-1;i++)cin>>a[i],in[a[i]]++;
		int minn;
		for(int i=1;i<=n-1;i++)
		if(!in[i]){
			minn=i;break;
		}
		int now=minn;
		while(cnt<n-2){
			ans[++cnt]=a[now];
			in[a[now]]--;
			if(!in[a[now]]&&a[now]<minn)now=a[now];
			else{
				minn++;
				while(in[minn])minn++;
				now=minn;
			}
		}
		int res=0;
		for(int i=1;i<=n-2;i++)
		res^=(i*ans[i]);
		cout<<res;
	}else{
		for(int i=1;i<=n-2;i++)cin>>a[i],in[a[i]]++;
		a[n-1]=n;in[n]++;
		int minn;
		for(int i=1;i<=n-1;i++)
		if(!in[i]){
			minn=i;break;
		}
		int now=minn;
		for(int i=1;i<=n-1;i++){
			ans[now]=a[i];
			in[a[i]]--;
			if(!in[a[i]]&&a[i]<minn)now=a[i];
			else{
				minn++;
				while(in[minn])minn++;
				now=minn;
			}
		}
		int res=0;
		for(int i=1;i<=n-1;i++)
		res^=(i*ans[i]);
		cout<<res;
	} 
     return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 42ms, 内存消耗: 2784K, 提交时间: 2022-08-19 20:35:38

#include<bits/stdc++.h>
using namespace std ;
const int N = 5e6 + 5 ;
#define ll long long
int n,m ;
int f[N],d[N],p[N] ;
ll ans=0 ;
void TP()
{
	for(int i=1;i<n;++i) scanf("%d",&f[i]),d[f[i]]++ ;
	for(int i=1,j=1;i<=n-2;++i,++j)
	{
		while(d[j]) ++j ; p[i]=f[j] ;
		while(i<=n-2&&!--d[p[i]]&&p[i]<j) p[i+1]=f[p[i]],++i ;
	}
	for(int i=1;i<=n-2;++i) ans^=1ll*i*p[i] ;
}
void PT()
{
	for(int i=1;i<=n-2;++i) scanf("%d",&p[i]),++d[p[i]] ;
	p[n-1]=n ;
	for(int i=1,j=1;i<n;++i,++j)
	{
		while(d[j]) ++j ; f[j]=p[i] ;
		while(i<n&&!--d[p[i]]&&p[i]<j) f[p[i]]=p[i+1],++i ;
	}
	for(int i=1;i<n;++i) ans^=1ll*i*f[i] ;
}
int main()
{
	scanf("%d%d",&n,&m) ;
	if(m==1) TP() ;
	else PT() ;
	printf("%lld\n",ans) ;
	return 0 ;
}