Bedao Grand Contest 16 - Thưởng Tết

View as PDF

Submit solution


Points: 1.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Tập đoàn XYZ bao gồm một chủ tịch và ~n~ nhân viên, được đánh số từ ~1~ đến ~n~. Tập đoàn hoạt động theo mô hình cấp trên — cấp dưới, cấp trên trực tiếp của nhân viên ~i~ là ~p_i~ (nếu ~p_i = 0~ thì cấp trên trực tiếp chính là chủ tịch). Theo đó nếu ~p_i \neq 0~ thì nhân viên ~i~ cũng được coi là cấp dưới trực tiếp của nhân viên ~p_i~. Năng suất lao động của nhân viên ~i~ được đánh giá bằng điểm số ~a_i~, năng suất càng cao thì điểm càng cao.

Năm mới sắp đến, chủ tịch tập đoàn chuẩn bị thưởng Tết cho các nhân viên. Nhân viên ~i~ sẽ hài lòng với mức thưởng Tết của mình nếu không có nhân viên nào khác là cấp trên trực tiếp hay cấp dưới trực tiếp của nhân viên ~i~ (trừ chủ tịch) có năng suất thấp hơn mà nhận được mức thưởng Tết cao hơn nhân viên ~i~.

Để tránh hiện tượng nhảy việc sau Tết, chủ tịch quyết định mức thưởng Tết để làm hài lòng tất cả các nhân viên. Vì ngân sách có hạn, mức thưởng của nhân viên ~i~ là một số nguyên dương không vượt quá ~m~, và không có hai nhân viên nào khác nhau mà có mức thưởng giống nhau. Chủ tịch tập đoàn muốn biết: có bao nhiêu cách thưởng Tết cho nhân viên mà tất cả đều hài lòng? Hai cách thưởng Tết được coi là khác nhau nếu có một nhân viên nhận được hai mức thưởng khác nhau trong hai cách.

Gọi ~S~ là số cách thưởng Tết cho nhân viên thỏa mãn các điều kiện trên. Vì ~S~ có thể rất lớn, hãy in ra phần dư của ~S~ khi chia cho ~998244353~.

Input

Dòng đầu chứa hai số nguyên ~n~ và ~m~ (~1 \leq n \leq 3000, n \leq m \leq 10 ^ 6~) lần lượt là số nhân viên trong tập đoàn và giới hạn mức thưởng Tết của từng người.

Dòng thứ hai chứa ~n~ số nguyên ~p_1, p_2, ..., p_n~ (~0 \leq p_i < i~) mô tả cấp trên trực tiếp của từng nhân viên.

Dòng thứ ba chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq n~) mô tả điểm số của từng nhân viên. Không có hai nhân viên nào khác nhau có cùng điểm số.

Output

In ra một số nguyên duy nhất là phần dư của ~S~ khi chia cho ~998244353~.

Scoring

Subtask Điểm Giới hạn
1 ~10\%~ ~n, m \le 9~.
2 ~10\%~ ~p_i = 0~ với mọi ~i~ thỏa mãn ~1 \leq i \leq n~.
3 ~20\%~ ~p_i = i - 1~ với mọi ~i~ thỏa mãn ~1 \leq i \leq n~.
4 ~20\%~ ~a_i = i~ với mọi ~i~ thỏa mãn ~1 \leq i \leq n~.
5 ~20\%~ ~n \le 200~.
6 ~20\%~ Không có ràng buộc gì thêm.

Sample Input 1

5 5
0 1 2 3 2
2 5 3 1 4

Sample Output 1

12

Sample Input 2

5 5
0 1 2 0 4
2 1 3 5 4

Sample Output 2

20

Notes

Ở test ví dụ thứ nhất:

Một số cách thưởng Tết cho nhân viên thỏa mản các điều kiện:

  • (2, 5, 3, 1, 4)

  • (1, 5, 4, 2, 3)

  • (3, 5, 4, 2, 1)

  • ...

Ở test ví dụ thứ hai:

Một số cách thưởng Tết cho nhân viên thỏa mản các điều kiện:

  • (2, 1, 3, 5, 4)

  • (2, 1, 5, 4, 3)

  • (4, 1, 2, 5, 3)

  • (4, 2, 3, 5, 1)

  • (5, 1, 4, 3, 2)

  • ...


Comments

Please read the guidelines before commenting.


There are no comments at the moment.