PreVOI 2025 - Sumprod
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho mảng ~A~ gồm ~n~ phần tử. Có ~q~ thao tác, mỗi thao tác thuộc ~2~ loại:
~1~ ~l~ ~r~ ~x~: Tăng giá trị các phần tử ~A_l, A_{l+1}, \dots, A_r~ lên ~x~.
~2~ ~l~ ~r~: Tính và in ra tổng các tích ~A_i \cdot A_j~ thỏa mãn ~l \le i \le j \le r~ và ~j-i \ge k~. Nói cách khác, tính:
~\sum_{i=l}^{r} \sum_{j=i+k}^{r} A_i \cdot A_j~.
Do đáp án của truy vấn loại ~2~ có thể lớn, hãy in ra đáp án sau khi chia lấy dư cho ~998244353~.
Input
Dòng đầu tiên ghi ~3~ số ~n, q, k~ ~(1 \le n, q \le 10^5, 1 \le k \le 5)~.
Dòng tiếp theo ghi ~n~ số lần lượt là giá trị của ~A_1, A_2, \dots, A_n~ ~(0 \le A_i < 998244353)~.
~q~ dòng tiếp theo, mỗi dòng ghi một truy vấn có cấu trúc như trong đề bài.
Trong các truy vấn, dữ liệu đảm bảo ~1 \le l \le r \le n~ và ~0 < x < 998244353~.
Output
Với mỗi truy vấn loại ~2~, in ra trên một dòng đáp án của truy vấn.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~10\%~ | ~n, q \le 200~ |
| 2 | ~20\%~ | ~n, q \le 5000~ |
| 3 | ~20\%~ | ~k = 1~ |
| 4 | ~20\%~ | ~n, q \le 5 \cdot 10^4~ |
| 5 | ~30\%~ | Không có giới hạn gì thêm |
Sample Input 1
5 5 2
1 2 3 4 5
2 1 4
2 2 5
1 2 4 2
2 1 4
2 2 5
Sample Output 1
15
33
35
69
Bình luận