Hướng dẫn cho TLEOJ Cup 2024 - Ngày 2 - Xúc xắc

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Sunlight

Tóm tắt đề: Đếm số dãy $a_1, a_2, ..., a_P$ với $1 \le a_i \le 6$ và $a_1 \times a_2 \times ... \times a_P = 2^L3^V5^H$ .

Lời giải

Subtask 1:

$P = 1$

Do $n = 1$ nên $1 \le a_1 \le 6$ . Ta chỉ cần kiểm tra xem $D$ có $\le 6$ hay không.

Subtask 2:

$V = H = 0, P = L$

Ở subtask này chỉ có một cách duy nhất đó là gieo ra toàn $5$ . In ra $1$ để AC subtask.

Subtask 3:

$P \le 9$

Sử dụng đệ quy quay lui và kiểm tra từng trường hợp.

Subtask 4 + 5:

$P, L, V, H \le 100$

Sử dụng quy hoạch động:
- $dp[x][y][z][t]$ là số cách gieo $x$ lần để được tích các chấm là $2^y3^z5^t$ . Với mỗi trạng thái, xét tất cả các trường hợp lần gieo tiếp theo ra các số từ $1$ đến $6$ .
- Nhận thấy rằng $dp[x]$ chỉ cần tính từ $dp[x - 1]$ nên ta có thể giảm bớt một chiều bộ nhớ.

Subtask 7:

$V = H = 0$

Ở trường hợp này số cách gieo là $C_P^L$ vì có chính xác $L$ vị trí gieo ra số $5$ và tất cả các vị trí còn lại đều phải gieo ra $1$ .

Subtask 8:

$H = 0$

Tương tự subtask 6, trong trường hợp này ta sẽ chon $L$ vị trí gieo ra $5$ và $V$ vị trí gieo ra $3$ . Đáp án là $C_P^L \times C_{P - L}^{V}$ .

Subtask 6:

$P, L, V, H \le 1000$

Gọi $u, v$ lần lượt là số vị trí gieo ra $4$ và $6$ . Khi đó số vị trí gieo ra $2, 3, 5$ cũng đã được xác định. Sử dụng tổ hợp như subtask 8 để giải quyết.

Subtask 9:

$V = 0$

Gọi $t$ là số lần gieo ra $4$ , thì số lần gieo ra $2$ là $H - 2t$ và số cách chọn là $C_P^L \times C_{P - L}^{t} \times C_{P - L - t}^{H - 2t}$ . Duyệt tất cả các giá trị $t$ thỏa mãn.

Subtask 10 + 11 + 12: Không có giới hạn gì thêm.

Ta tách các số từ 1 đến 6 thành bốn nhóm:
- Nhóm 1: ${1}$ .
- Nhóm 2: ${2, 4}$ .
- Nhóm 3: ${3, 6}$ ,
- Nhóm 4: ${5}$ .
Với mỗi $a_i$ , ta lựa chọn nhóm mà nó thuộc về. Nếu $a_i$ thuộc nhóm 1, ta không mất thừa số nào. Nếu $a_i$ thuộc nhóm 2, ta mất một thừa số $2$ . Nếu $a_i$ thuộc nhóm 3, ta mất một thừa số $3$ . Nếu $a_i$ thuộc nhóm 4, ta mất một thừa số $5$ .
Chú ý rằng có thể có ít hơn $H$ số thuộc nhóm 2, từ đó ta sẽ còn dư ra một số thừa số $2$ . Các thừa số này sẽ được dùng để "nâng cấp" các số trong nhóm $2$ và $3$ - từ $2$ lên $4$ và từ $3$ lên $6$ .
Như vậy, ta có thể duyệt mọi số $t$ là số lượng số thuộc nhóm 2 rồi áp dụng các ý tưởng tổ hợp để giải quyết bài toán.
Lưu ý rằng, do $P, L, V, H \le 2 \times 10^7$ nên ta phải lập trước một mảng $fact[i] = i! \mod 20071409$ và $inv[i]$ là nghịch đảo của $fac[i]$ . Mảng $inv[i]$ phải được tính trong $O(P)$ bằng nhận xét $inv[i] = inv[i + 1] \times (i + 1)$ .

Bình luận

Không có bình luận nào.