PreVOI 2025 - Sumprod

Xem dạng PDF

Gửi bài giải

Điểm: 60,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong 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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.