基于大序列和异或运算的问题最有效的实现方式

Question

我得到了以下输入：

n 其中 n 是序列的大小
k 是一个整数
一个序列A[0] A[1] A[2] ...............A[n-1]

我需要为每个 i 执行从 0 到 (k-1) 的计算

   find a,b
   where a=A[i%n] and b=A[n-(i%n)-1]
   then set A[i%n]=a XOR b

并输出最终序列space分开

订单已下达：-

 n<=10^4
 k<=10^12
 Ai<=10^7 for each i

i have applied the naive approach

n,k=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(k):
    t=i%n
    arr[t]=arr[t]^arr[n-(t)-1]
for i in arr:
    print(i,end=" ")

但它显示大型测试用例超出了时间限制。

想要一个有效的实施建议

Answer 1

**

Re:Updated implementation approach for the problem

**

合并算法后建议我

@AJNeufeld and @vujazzman

如果循环是运行到 (N*3)

的任意倍数，则序列保持不变

因此我们可以为 k

的所有值节省运行ning 的开销

而是找到最接近 (n*3) to K 的倍数，然后 run loop for remaining value from the found multiple to k

注意：- 奇数n个案由set A[n//2] = 0

提前单独处理

所以我想出了以下实现：

for _ in range(int(input())):
    n,k=map(int,input().split())
    arr=list(map(int,input().split()))
    if n % 2 and k > n//2 :           #odd n case
        arr[ n//2 ] = 0
    rem= k % ( 3*n )
    closest_multiple_3n = ( k-rem )
    for i in range( closest_multiple_3n,k ):
        t=i % n
        arr[t] ^= arr[-1-t]
    print(*arr)

我已经创建了一些自制的测试用例，例如：-

t=1
n=11 k=9999999998
A[] = 20 7 27 36 49 50 67 72 81 92 99

output:- 20 7 27 36 49 0 67 72 81 92 119

note :- closest_multiple_3n = 9999999966
         rem = 32
        (20^92=119)

不到 1 秒即可完美运行

基于大序列和异或运算的问题最有效的实现方式

Most effective way to implement problem based on large sequence and xor operation

python

xor