// by Isaunoya
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (register int i = (x); i <= (y); ++i)
#define Rep(i, x, y) for (register int i = (x); i >= (y); --i)
//#define int long long
const int _ = 1 << 21;
struct I {
char fin[_], *p1 = fin, *p2 = fin;
inline char gc() { return (p1 == p2) && (p2 = (p1 = fin) + fread(fin, 1, _, stdin), p1 == p2) ? EOF : *p1++; }
inline I& operator>>(int& x) {
bool sign = 1; char c = 0;
while (c < 48) ((c = gc()) == 45) && (sign = 0);
x = (c & 15); while ((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15);
x = sign ? x : -x;
return *this;
}
inline I& operator>>(unsigned& x) {
bool sign = 1; char c = 0;
while (c < 48) ((c = gc()) == 45) && (sign = 0);
x = (c & 15);
while ((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15);
x = sign ? x : -x;
return *this;
}
inline I& operator>>(double& x) {
bool sign = 1; char c = 0;
while (c < 48) ((c = gc()) == 45) && (sign = 0);
x = (c - 48); while ((c = gc()) > 47) x = x * 10 + (c - 48);
if (c == '.') {
double d = 1.0; while ((c = gc()) > 47) d = d * 0.1, x = x + (d * (c - 48));
}
x = sign ? x : -x;
return *this;
}
inline I& operator>>(char& x) {
do x = gc(); while (isspace(x));
return *this;
}
inline I& operator>>(string& s) {
s = ""; char c = gc();
while (isspace(c)) c = gc();
while (!isspace(c) && c != EOF) s += c, c = gc();
return *this;
}
} in;
struct O {
char st[100], fout[_];
signed stk = 0, top = 0;
inline void flush() {
fwrite(fout, 1, top, stdout), fflush(stdout), top = 0;
}
inline O& operator<<(long long x) {
if (top > (1 << 20)) flush();
if (x < 0) fout[top++] = 45, x = -x;
do
st[++stk] = x % 10 ^ 48, x /= 10;
while (x);
while (stk) fout[top++] = st[stk--];
return *this;
}
inline O& operator<<(char x) {
fout[top++] = x;
return *this;
}
inline O& operator<<(string s) {
if (top > (1 << 20)) flush();
for (char x : s) fout[top++] = x;
return *this;
}
} out;
#define pb emplace_back
#define fir first
#define sec second
template < class T > inline void cmax(T x , const T & y) {
(x < y) && (x = y) ;
}
template < class T > inline void cmin(T x , const T & y) {
(x > y) && (x = y) ;
}
const int N = 5e5 + 10 , L = 20 ;
struct Edge {
int v , nxt ;
} e[N << 1] ;
int head[N] , cnt = 0 ;
int n , q , rt = 0 , lastans = 0 , fa[N][L + 1] , lg[N] ;
vector < int > up[N] , down[N] ;
inline void add(int u , int v) { e[++ cnt] = { v , head[u] } , head[u] = cnt ; }
using u = unsigned ;
u s ;
inline u get(u x) { return x ^= x << 13 , x ^= x >> 17 , x ^= x << 5 , s = x ; }
int p[N] , dep[N] , _dep[N] , son[N] , top[N] , col[N] ;
void dfs(int u , int d) {
dep[u] = _dep[u] = d ; register int v = 0 ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
dfs((v = e[i].v) , d + 1) ;
if(dep[v] > dep[u]) { dep[u] = dep[v] ; son[u] = v ; }
}
}
void dfs2(int u , int t) {
if(u == (top[u] = t)) {
for(register int i = 0 , v = u ; i <= dep[u] - _dep[u] ; i ++) up[u].pb(v) , v = p[v] ;
for(register int i = 0 , v = u ; i <= dep[u] - _dep[u] ; i ++) down[u].pb(v) , v = son[v] ;
}
if(son[u]) dfs2(son[u] , t) ; register int v = 0 ;
for(register int i = head[u] ; i ; i = e[i].nxt) if((v = e[i].v) != son[u]) dfs2(v , v) ;
}
using ll = long long ;
ll ans ;
inline int qry(int x , int k) {
if(! k) return x ;
x = fa[x][lg[k]] , k -= 1 << lg[k] , k -= _dep[x] - _dep[top[x]] , x = top[x] ;
return k >= 0 ? up[x][k] : down[x][- k] ;
}
signed main() {
#ifdef _WIN64
freopen("testdata.in" , "r" , stdin) ;
#endif
in >> n >> q >> s ;
lg[1] = 0 ; rep(i , 2 , n) lg[i] = lg[i >> 1] + 1 ;
rep(i , 1 , n) { in >> p[i] ; (fa[i][0] = p[i]) ? add(p[i] , i) , 0 : (rt = i) ; }
dfs(rt , 1) , dfs2(rt , rt) ; rep(j , 1 , lg[n]) rep(i , 1 , n) fa[i][j] = fa[fa[i][j - 1]][j - 1] ;
register int x , k ;
rep(i , 1 , q) { x = (get(s) ^ lastans) % n + 1 , k = (get(s) ^ lastans) % _dep[x] ; ans ^= 1ll * i * (lastans = qry(x , k)) ; }
out << ans << '
' ;
return out.flush(), 0;
}
接着咕咕咕