CFR 768 C. Jon Snow and his Favourite Number ( DP )

Problem - C - Codeforces

題意：
給一個長度為 N 的數列，要做 K 次操作。每次將數列排序後，奇數項 ( 1 based ) 和 X 做 xor，偶數項不變。問所有操作結束後，數列的長相。

資料規模：
First line consists of three integers n, k, x (1 ≤ n ≤ 1e5, 0 ≤ k ≤ 1e5, 0 ≤ x ≤ 1e3) — number of rangers Jon has, the number of times Jon will carry out the operation and Jon's favourite number respectively.
Second line consists of n integers representing the strengths of the rangers a1, a2, ..., an (0 ≤ ai ≤ 1e3).

解法：
注意到 X 和 A 的取值在 1000 以下，因此數列中任意時刻的最大值為 1023。考慮以值的出現次數作為單位進行處理。
用 python 很難過，連本機跑都快一分鐘。神秘的 pypy3 可以讓相同的代碼得到 AC。

時間 / 空間複雜度：
O( K * 1023 )

N, K, X = map( int, input().split() )
A = list( map( int, input().split() ) )

freq = [ [ 0 for i in range( 1024 ) ], [ 0 for i in range( 1024 ) ] ]
for i in range( N ):
  freq[ 0 ][ A[ i ] ] += 1

for i in range( K ):
  for j in range( 1024 ):
    freq[ ~ i & 1 ][ j ] = 0
  ctr = 0
  for j in range( 1024 ):
    if ctr == 0:
      freq[ ~ i & 1 ][ j ^ X ] += freq[ i & 1 ][ j ] + 1 >> 1
      freq[ ~ i & 1 ][ j ] += freq[ i & 1 ][ j ] >> 1
    else:
      freq[ ~ i & 1 ][ j ] += freq[ i & 1 ][ j ] + 1 >> 1
      freq[ ~ i & 1 ][ j ^ X ] += freq[ i & 1 ][ j ] >> 1
    ctr ^= freq[ i & 1 ][ j ] & 1

minv, maxv = 1023, 0
for i in range( 1024 ):
  if freq[ K & 1 ][ i ] == 0: continue
  minv = min( minv, i )
  maxv = max( maxv, i )

print( maxv, minv )