2次元正方形（n * n）の行列を与えられたO（n^2）

Question

よりも複雑な行列演算を最適化するには、行列の上三角の演算を行う方法があるかどうかを調べようとしています。O（n^2）時間未満[好ましくは線形時間]。行列要素はexample.i.eに示すように連続していることに注意してください。各行と列のすべての値がソートされます。これをO（n^2）の複雑さを使って解決しました。以下の例： 21^22^23^24^25^26 ^：私は上三角に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を意味します27^28^29^31^32^33^36^37^41 = 35であり、これは所望の結果である。すなわち

、私は基本的にXOR-ING午前：

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

Iは、それらのバイナリ等価物を生成することによって、パターンを見つけることによりDPを使用して解決しようとしたが、任意の一貫したパターンを見つけることができませんでした。コメントの後

Answer 1

編集：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); 
} 

からメソッドを使用して

は、このようなループを作成します。

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

あなたが唯一それぞれの最初の値をループにする必要があります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