打个表发现有循环节,然后我就 naive 地觉得循环节大小一定是 $2$ 导致爆了 OJ。
发现循环节的长度不会超过 $200$。于是就可以暴力 $200$ 次找出循环节来然后做。这样的复杂度是 $O(200\cdot n)$ 的。
关于循环节,个人的理解仅限于 `xor` 运算有自反性,所以显然循环节应该是偶数长度的。
…不会编了。就当是一个乱搞吧= =
话说我确实没怎么写过乱搞,业务生疏.jpg
```cpp
int cnt ;
int p, q ;
int n, k, m ;
int rec[M][N] ;
int base[N] ;
int buc[N] ;
int cycle ;
bool cmp(int *a, int *b){
for (int i = 1 ; i <= n ; ++ i)
if (a[i] != b[i]) return 0 ;
return 1 ;
}
int cmp_rec(int *a){
for (int i = 0 ; i < cnt ; ++ i)
if (cmp(rec[i], a)) return i ;
return -1 ;
}
int main(){
cin >> n >> k >> m ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = qr() ; p = -1, q = P ;
sort(base + 1, base + n + 1) ;
memcpy(rec[0], base, sizeof(base)) ;
if (!k){
for (int i = 1 ; i <= n ; ++ i)
chkmax(p, base[i]), chkmin(q, base[i]) ;
cout << p << " " << q << '\n' ;
return 0 ;
}
while (k){
-- k ; ++ cnt ; //debug(cnt) ;
for (int i = 1 ; i <= n ; ++ i)
rec[cnt][i] = rec[cnt - 1][i] ^ (i & 1) * m ;
sort(rec[cnt] + 1, rec[cnt] + n + 1) ; //debug(rec[cnt], 1, n) ;
if ((cycle = cnt - cmp_rec(rec[cnt])) <= cnt) break ;
}
if (k)
k %= cycle, cnt -= cycle - k ;
for (int i = 1 ; i <= n ; ++ i){
chkmax(p, rec[cnt][i]) ;
chkmin(q, rec[cnt][i]) ;
}
cout << p << " " << q << '\n' ;
}
```