Tổng hai chéo ma trận bản 2

Time limit: 1.0s , Memory limit: 256M , Points: 20 (partial)

Cho ma trận vuông kích thước $n$ ~n~. Bi lập ma trận bằng cách điền các con số từ $1$ ~1~ đến $n^2$ ~n^2~ vào ma trận theo thứ tự lần lượt từ trái sang phải và từ trên xuống. Ví dụ với ma trận $n = 3$ ~n = 3~, ta có ma trận sau:

$\displaystyle \begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{bmatrix}$

Với ma trận vuông ở trên, người ta đưa ra hai khái niệm là:

Đường chéo chính là các phần tử mà chỉ số $i = j$ ~i = j~.
Đường chéo phụ là các phần tử mà chỉ số $i = n-1-j$ ~i = n-1-j~.

Cho trước số nguyên dương $n$ ~n~, hãy giúp Bi tính tổng các phần tử trên hai đường chéo của ma trận.

Input

Dòng đầu tiên chứa số $T$ ~T~ là số testcase thỏa $1 \le T \le 10$ ~1 \le T \le 10~.

$T$ ~T~ dòng tiếp theo, mỗi dòng chứa các số nguyên $n$ ~n~ là kích thước ma trận thỏa $2 \le n \le 10^{15}$ ~2 \le n \le 10^{15}~.

Output

Ứng với mỗi testcase in tổng cần tìm trên từng dòng, vì số lớn nên chia cho $10^9 + 7$ ~10^9 + 7~.

Samples

Sample Input 1

2
3
10

Sample Output 1

25
1010

Comments

0

Kuro_Neko commented on Nov. 9, 2023, 4:11 p.m.

để ý thấy khi vẽ ma trận bằng tay, các phần tử trên đường chéo chính cách nhau một lượng không đổi là (kích thước của ma trận vuông +1) vd: ma trận vuông 3 thì a[i+1][j+1]-a[i][j] = 4, và phần đường chéo phụ: các phần tử cách nhau = kích thước của ma trận vuông. tổng các phần tử trên đường chéo chính là một cấp số cộng với n phần tử. với u1= 1 và un= (kích thước ma trận bình phương). ở phần đường chéo phụ cũng vậy nhưng ngược lại. và phần cuối cùng. khi kích thước của ma trận là một số lẻ (%2!=0) thì có sự lặp lại của phần tử ở giữa của ma trận đó nên trừ đi phần tử ở giữa đó. (vì nó xuất hiện 2 lần trong công thức tính cấp số cộng). tổng kết : dùng công thức cấp số cộng để tính tổng trên đường chéo chính, tương tự với đường chéo phụ, và nếu kích thước của ma trận đó là một số lẻ thì trừ đi một lượng là phần tử ở chính giữa ma trận đó

Link

1

Kuro_Neko commented on Nov. 9, 2023, 4:17 p.m.

nhân tiện thì nên dùng python (hoặc ngôn ngữ hỗ trợ số nguyên lớn) để làm bài này (hoặc không). nếu dùng c++ để code thì cần thêm "lý thuyết đồng dư" để code

Link