2 차원 정사각형 (n * n) 행렬을 주어진 O (n^2)

Question

미만의 복잡도로 행렬 연산을 최적화하려면 행렬의 위쪽 삼각형에 연산을 수행하는 방법이 있는지 찾으려고 노력 중입니다. O (n^2) 시간 미만 [바람직하게는 선형 시간]. 행렬 요소는 example.i.e와 같이 연속적입니다. 각 행과 열의 모든 값이 정렬됩니다.이 문제는 O (n^2) 개의 복잡도를 사용하여 해결되었습니다. 아래의 예 : I 상부 삼각형에 XOR 연산을 수행 할 경우

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

지금

는, 그 아래의 요소 -ing XOR를 의미 : 21^22^23^24^25^26^27^28^29^31^32^33^36^37^41 = 35 이는 원하는 결과입니다. 즉

, 나는 기본적으로 XOR 한창입니다 :

21 22 23 24 25 26 27 28 29 31 32 33 36 37 41

내가 그들의 이진 등가물을 생성하여 패턴을 찾아 DP를 사용하여 해결하려고했으나 어떤 일관된 패턴을 찾을 수 없습니다. 주석 후

Answer 1

편집 :

long FinalXor = 0; 
for(int i = 0 ; i< n; i++){ 
    FinalXor =FinalXor^getXor(m(i,0),m(i,0)+ n-i) 
} 

당신은 각의 첫 번째 값을 통해 루프를해야합니다

방법을 사용하여 this post

long long f(long long a) { 
    long long res[] = {a,1,a+1,0}; 
    return res[a%4]; 
} 

long long getXor(long long a, long long b) { 
    return f(b)^f(a-1); 
} 

에서이 같은 루프를 만들 O (n)의 복잡도를 갖는 알고리즘을 생성하는 행

Answer 2

그리드의 숫자 패턴에 대한 제약 조건이 주어지면 O (n) 시간에이 작업을 수행 할 수있는 방법이 있습니다. 먼저 O (1) 시간의 [1, n]에있는 모든 숫자의 x 또는 합계 결과를 얻을 수있는 함수를 작성해야합니다.

//iteratate in every row of the grid to find out xor sum of that row 
//and xor add that sum with the final_xorsum 
int final_xorsum=0; 
for(i=0;i<n;i++) { 
    final_xorsum^=xor_sum(biggest_num_in_row_i)^xor_sum(smallest_num_in_row_i-1); 
} 
cout<<final_xorsum<<endl; 

//this function will retrun xor sum value of all the numbers [1...n] 
//example: xor_sum(5) = 1^2^3^4^5 
int xor_sum(int n) { 
    int vals[4] = {a,1,a+1,0}; 
    return vals[a%4]; 
} 

는 xor_sum 기능에 대한 자세한 내용은 여기 읽기 : Find XOR of all numbers in a given range