Phân Phối Quà Tặng (Gold)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có $N$ món quà (đánh số từ $1$ đến $N$ ) cho $N$ con bò (đánh số từ $1$ đến $N$ ). Mỗi con bò có một danh sách ưu tiên, là hoán vị của $N$ món quà. Ban đầu, quà $i$ được trao cho bò $i$ .

Các con bò có thể trao đổi quà với điều kiện: mỗi con bò phải nhận được cùng món quà ban đầu hoặc một món quà ưa thích hơn.

Tuy nhiên, mỗi con bò thuộc một trong hai giống: Holstein (H) hoặc Guernsey (G). Một món quà chỉ có thể được trao cho con bò cùng giống với con bò ban đầu nhận nó.

Cho $Q$ truy vấn, mỗi truy vấn chỉ định giống của từng con bò. Với mỗi truy vấn, đếm số cách phân phối quà hợp lệ.

Dữ liệu vào

Dòng 1: Số nguyên $N$
$N$ dòng tiếp theo: Danh sách ưu tiên của bò $i$
Dòng $N + 2$ : Số nguyên $Q$
$Q$ dòng tiếp theo: Xâu ký tự 'G' và 'H' độ dài $N$ , chỉ định giống của mỗi con bò

Dữ liệu ra

$Q$ dòng, mỗi dòng là số cách phân phối hợp lệ cho truy vấn tương ứng.

Ràng buộc

$1 \leq N \leq 18$
$1 \leq Q \leq min (10^{5}, 2^{N})$

Ví dụ

Input	Output	Giải thích
4 1 2 3 4 1 3 2 4 1 2 3 4 1 2 3 4 5 HHHH HHGG GHGH HGGG GHHG	2 1 1 2 2	Với "HHHH": 2 cách — giữ nguyên hoặc bò 2 đổi với bò 3. Với "HHGG": chỉ 1 cách — giữ nguyên (bò 2 và 3 khác giống nên không đổi được).

Bình luận

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