โจทย์: สร้าง matrix A (row-major 1..N) และ B (column-major 1..N) หา trace ของ C = A + B (trace = ผลรวม diagonal elements)
ตัวอย่าง: 6×9 matrix → trace = 384
สูตรทางคณิตศาสตร์
A[i][j] = i×C + j + 1 (0-indexed, C = columns)
B[i][j] = j×R + i + 1 (R = rows)
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]
ตัวอย่างโค้ด C++ (Direct Calculation)
#include <bits/stdc++.h>
using namespace std;
long long calculateMatrixTrace(int R, int C) {
int n = min(R, C);
long long sum = 0;
for (int i = 0; i < n; i++) {
long long a = i * C + i + 1;
long long b = i * R + i + 1;
sum += a + b;
}
return sum;
}
int main() {
cout << calculateMatrixTrace(6, 9) << endl; // 384
}
อินพุต
6, 9
เอาต์พุท
384
Complexity
- Time: O(min(R,C)) หรือ O(1) ด้วยสูตร arithmetic series
- Space: O(1)
