Tính trace ma trận tổng của thứ tự hàng và cột (Row-major + Column-major) trong C++

Cho ma trận kích thước R x C. Tạo ma trận A (điền theo hàng), B (điền theo cột), C = A + B. Tính trace của C (tổng đường chéo chính).

Công thức toán học

A[i][j] = i*C + j + 1

B[i][j] = j*R + i + 1

C[i][i] = A[i][i] + B[i][i] = (i*C + i + 1) + (i*R + i + 1) = i*(R+C+2) + 2

Trace = Σ_{i=0..min(R,C)-1} [i*(R+C+2) + 2]

= (R+C+2) * Σi + 2*min(R,C)

= (R+C+2) * min(R,C)*(min(R,C)-1)/2 + 2*min(R,C)

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

long long matrixTrace(int R, int C) {
    int k = min(R, C);
    long long sum_i = 1LL * k * (k - 1) / 2;
    return 1LL * (R + C + 2) * sum_i + 2LL * k;
}

int main() {
    cout << matrixTrace(6, 9) << endl; // 384
    return 0;
}

Kết quả

384

Độ phức tạp: O(1) thay vì O(R*C) xây dựng ma trận.