Tổng Trọng Số Khoảng Cách Dãy Số
Xem PDF
Điểm:
1900
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên \(A = (A_1, A_2, \dots, A_N)\) gồm \(N\) phần tử.
Với mỗi số nguyên \(k\) từ \(1\) đến \(N - 1\), hãy tính giá trị \(S_k\) được định nghĩa theo công thức sau:
\[S_k = \sum_{i=1}^{N-k} (A_{i+k} - A_i)^2 \cdot (A_{i+k} + A_i)\]
Vì giá trị \(S_k\) có thể rất lớn, hãy in ra kết quả của từng \(S_k\) sau khi lấy dư cho \(998244353\).
Input
- Dòng đầu tiên chứa số nguyên \(N\) (\(2 \le N \le 2 \cdot 10^5\)).
- Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(0 \le A_i < 998244353\)).
Output
- In ra trên một dòng gồm \(N - 1\) số nguyên \(S_1, S_2, \dots, S_{N-1}\) phân tách bởi dấu cách, đại diện cho đáp án tìm được sau khi lấy dư cho \(998244353\).
Example
Test 1
Input
4
1 2 4 3Output
34 50 16Note
- Với \(k = 1\):
- \(i = 1\): \((2 - 1)^2 \cdot (2 + 1) = 1 \cdot 3 = 3\)
- \(i = 2\): \((4 - 2)^2 \cdot (4 + 2) = 4 \cdot 6 = 24\)
- \(i = 3\): \((3 - 4)^2 \cdot (3 + 4) = 1 \cdot 7 = 7\)
- \(S_1 = 3 + 24 + 7 = 34\).
- Với \(k = 2\):
- \(i = 1\): \((4 - 1)^2 \cdot (4 + 1) = 9 \cdot 5 = 45\)
- \(i = 2\): \((3 - 2)^2 \cdot (3 + 2) = 1 \cdot 5 = 5\)
- \(S_2 = 45 + 5 = 50\).
- Với \(k = 3\):
- \(i = 1\): \((3 - 1)^2 \cdot (3 + 1) = 4 \cdot 4 = 16\)
- \(S_3 = 16\).
Scoring
- Subtask 1 (30 điểm): \(2 \le N \le 2000\)
- Subtask 2 (70 điểm): Không có ràng buộc gì thêm (\(2 \le N \le 2 \cdot 10^5\))
Bình luận