Trang chủ Bài tập Kỳ thi Bài nộp Xếp hạng Thảo luận Trợ giúp
Đăng nhập Đăng ký

#1557. SQUID - Trò chơi con mực

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI
Nộp bài Các bài nộp Bài nộp tốt nhất Bộ test Thảo luận

Đề bài

Nguồn: Contest PVH 2021 - 2022

Quá chán ghét và khiếp sợ trước những cảnh giết chóc man rợ trong series bom tấn của điện ảnh Hàn Quốc, các học sinh trường THPT Chuyên Ăn Mực quyết định chuyển sang mua mực về ăn.

\eta học sinh rủ nhau đi chợ mua mực, họ đã mua được một đàn mực siêu to khổng lồ với 2207^{1997} con mực một nắng cỡ 0.5 kg/con. Các bé quyết định làm bữa lẩu mực thập cẩm ăn cho đã đời.

Nồi lẩu đã lên bếp, nước dùng đã sôi thơm nức mũi, họ bắt đầu thả dần những con mực cùng viên chiên cá, xúc xích, rau, ngô và rất nhiều món ăn kèm khác vào nồi. Trong lúc chờ mực chín, cả nhóm đã bàn bạc và quyết định đề ra luật chơi cho "trò chơi ăn mực" này như sau: Bữa tiệc diễn ra trong \tau lượt. Tại mỗi lượt, mỗi bạn sẽ ăn một số mực tùy ý từ 0 đến \lambda ; nói cách khác, tại một lượt, một bạn có thể không ăn con mực nào hoặc ăn tối đa \lambda con. Các bạn thống nhất rằng, để những chú mực được ra đi thanh thản, linh hồn siêu thoát khi vào nồi lẩu, tất cả mọi người phải ăn mực nguyên con và không được xé hay thái nhỏ. Bởi thế, số con mực mỗi bạn ăn trong một lượt phải là số nguyên.

Cũng giống như tinh thần của series "trò chơi con mực", "trò chơi ăn mực" phải đảm bảo tính công bằng và xóa bỏ khoảng cách giữa kẻ giàu và người nghèo. Do đó, chênh lệch giữa tổng số con mực đã ăn (tính tới khi bữa lẩu kết thúc) của hai bạn bất kì không được quá \delta . Bằng tình bạn đẹp giữa mọi người, tất cả các bạn đều thú nhận công khai rằng, trong lúc chuẩn bị đồ lẩu, các bạn đã "ăn vụng" lần lượt \rho_1, \rho_2, \ldots, \rho_\eta con mực.

Như vậy, với việc có \lambda + 1 cách chọn số con mực sẽ ăn trong mỗi lượt (0, 1, 2, \ldots, \lambda) , mỗi người có tất cả (\lambda + 1)^\tau số khả năng lựa chọn cách ăn mực trong toàn bộ bữa tiệc; và cả bữa tiệc với \eta bạn sẽ có tất cả (\lambda + 1)^{\tau \cdot \eta} "kịch bản ăn mực" có thể xảy ra. Trong số các kịch bản này, hãy đếm số kịch bản sao cho sau khi bữa tiệc kết thúc, chênh lệch về tổng số mực đã ăn (bao gồm cả số mực trong nồi lẩu và số mực đã "ăn vụng" trước đó) giữa hai người bất kì không quá \delta .

Dữ liệu vào:

  • Dòng đầu tiên chứa bốn số nguyên \eta , \lambda , \tau và \delta (1 \leq \eta \leq 10^1, 1 \leq \lambda \leq 10^3, 1 \leq \tau \leq 10^2, 0 \leq \delta \leq 10^6) , lần lượt là số bạn tham dự bữa tiệc, số con mực tối đa mỗi bạn được ăn trong một lượt, số lượt ăn trong toàn bộ bữa lẩu và chênh lệch tổng số mực được ăn tối đa giữa hai bạn bất kì;
  • Dòng thứ hai chứa \eta số nguyên \rho_1, \rho_2, \ldots, \rho_\eta (0 \leq \rho_i \leq 10^7) trong đó \rho_i là số con mực bạn thứ i đã "ăn vụng" trong lúc chuẩn bị nồi lẩu.

Dữ liệu ra:

  • In ra một số nguyên duy nhất là số "kịch bản ăn mực" trong toàn bộ bữa tiệc thỏa mãn các điều kiện đề bài. Do kết quả có thể rất bé, bạn cần in ra theo modulo 998244353 .

Ví dụ:

Dữ liệu vào:

2 2 1 3
3 6

Dữ liệu ra:

6

Dữ liệu vào:

7 1 5 2
2 2 7 1 9 9 7

Dữ liệu ra:

0

Giải thích:

Trong ví dụ thứ nhất, cả bữa tiệc chỉ có \tau = 1 lượt ăn và trong lượt này mỗi bạn được ăn 0 , 1 hoặc 2 con mực. Do đó, có tất cả 9 "kịch bản ăn mực" có thể xảy ra với hai người:

  • Kịch bản 1 : Bạn thứ nhất ăn 0 con mực và bạn thứ hai ăn 0 con mực. Kết hợp với số lượng đã "ăn vụng" từ trước, hai bạn lần lượt ăn 3 + 0 = 3 và 6 + 0 = 6 con mực. Chênh lệch giữa hai bạn là |3 - 6| = 3 .
  • Kịch bản 2 : Bạn thứ nhất ăn 0 con mực và bạn thứ hai ăn 1 con mực. Kết hợp với số lượng đã "ăn vụng" từ trước, hai bạn lần lượt ăn 3 + 0 = 3 và 6 + 1 = 7 con mực. Chênh lệch giữa hai bạn là |3 - 7| = 4 .
  • Kịch bản 3 : Bạn thứ nhất ăn 0 con mực và bạn thứ hai ăn 2 con mực. Kết hợp với số lượng đã "ăn vụng" từ trước, hai bạn lần lượt ăn 3 + 0 = 3 và 6 + 2 = 8 con mực. Chênh lệch giữa hai bạn là |3 - 8| = 5 .
  • Kịch bản 4 : Bạn thứ nhất ăn 1 con mực và bạn thứ hai ăn 0 con mực. Kết hợp với số lượng đã "ăn vụng" từ trước, hai bạn lần lượt ăn 3 + 1 = 4 và 6 + 0 = 6 con mực. Chênh lệch giữa hai bạn là |4 - 6| = 2 .
  • Kịch bản 5 : Bạn thứ nhất ăn 1 con mực và bạn thứ hai ăn 1 con mực. Kết hợp với số lượng đã "ăn vụng" từ trước, hai bạn lần lượt ăn 3 + 1 = 4 và 6 + 1 = 7 con mực. Chênh lệch giữa hai bạn là |4 - 7| = 3 .
  • Kịch bản 6 : Bạn thứ nhất ăn 1 con mực và bạn thứ hai ăn 2 con mực. Kết hợp với số lượng đã "ăn vụng" từ trước, hai bạn lần lượt ăn 3 + 1 = 4 và 6 + 2 = 8 con mực. Chênh lệch giữa hai bạn là |4 - 8| = 4 .
  • Kịch bản 7 : Bạn thứ nhất ăn 2 con mực và bạn thứ hai ăn 0 con mực. Kết hợp với số lượng đã "ăn vụng" từ trước, hai bạn lần lượt ăn 3 + 2 = 5 và 6 + 0 = 6 con mực. Chênh lệch giữa hai bạn là |5 - 6| = 1 .
  • Kịch bản 8 : Bạn thứ nhất ăn 2 con mực và bạn thứ hai ăn 1 con mực. Kết hợp với số lượng đã "ăn vụng" từ trước, hai bạn lần lượt ăn 3 + 2 = 5 và 6 + 1 = 7 con mực. Chênh lệch giữa hai bạn là |5 - 7| = 2 .
  • Kịch bản 9 : Bạn thứ nhất ăn 2 con mực và bạn thứ hai ăn 2 con mực. Kết hợp với số lượng đã "ăn vụng" từ trước, hai bạn lần lượt ăn 3 + 2 = 5 và 6 + 2 = 8 con mực. Chênh lệch giữa hai bạn là |5 - 8| = 3 .

Ngoại trừ ba kịch bản số 2 , 3 và 6 , ở kịch bản còn lại số mực ăn được của hai bạn đều lệch nhau không quá \delta = 3 . Do đó, đáp số là 6 .

Trong ví dụ thứ hai, bạn thứ tư đã "ăn vụng" \rho_4 = 1 con mực và bạn thứ năm đã "ăn vụng" \rho_5 = 9 con mực. Cả bữa tiệc có \tau = 5 lượt ăn và ở mỗi lượt một bạn chỉ được ăn tối đa \lambda = 1 con mực. Như vậy, tổng số mực bạn thứ tư ăn được trong toàn bộ bữa tiệc không thể quá 6 con, trong khi bạn thứ năm chắc chắn ăn tối thiểu 9 con. Vì vậy, không thể xảy ra trường hợp số mực đã ăn của hai người này lệch nhau không quá \delta = 2 .

Giới hạn:

Bộ test của bài được chia làm các subtask như sau:

  • Subtask 1 ( \frac{4}{35} số điểm): \eta = 1
  • Subtask 2 ( \frac{6}{35} số điểm): \eta \leq 3 , \lambda \leq 6 , \tau \leq 3
  • Subtask 3 ( \frac{6}{35} số điểm): \eta \leq 2 , \lambda \leq 100 , \tau \leq 10
  • Subtask 4 ( \frac{6}{35} số điểm): \eta \leq 2
  • Subtask 5 ( \frac{6}{35} số điểm): \delta = 0
  • Subtask 6 ( \frac{1}{5} số điểm): Không có ràng buộc gì thêm.

Thể loại (tag)

Đang tải trình chỉnh sửa ...
Chuyên Sơn La Online Judge.
Mã nguồn mở cho giải pháp chấm bài trực tuyến (Online Judge): DMOJ - UOJ - QDUOJ - SYZOJ - OJS - SHARIF - AURORA - CMS