페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5324

선물 재분배2 (Redistributing Gifts) 2초 256MB

문제

농부 John은 1...N으로 번호가 매겨진 N마리의 소를 위해 N개의 선물(1≤N≤18)(또한 1...N로 번호가 지정됨)을 준비합니다. 각 소에는 N개의 모든 선물의 순열인 위시리스트가 있으며 소는 순열에서 나중에 나타나는 선물보다 먼저 나타나는 선물을 선호합니다.

농부 John​은 게을러서 그냥 소 i에게 선물 i를 할당합니다. 이제 소들은 스스로 모여서 선물을 재분배하기로 결정하여 재분배 후 각 소는 원래 받은 선물 또는 원래 받은 선물보다 더 좋아했던 선물로 끝납니다.

 

추가 제한 사항으로: 선물이 원래 소에게 할당된 경우 선물은 동일한 품종의 소에게만 재할당될 수 있습니다(각 소는 젖소(Holstein​) 또는 황소(Guernsey)). 길이가 N인 Q(1≤Q≤min(105,2n)) 기호 문자열이 주어지면 각 문자열에 해당하는 재할당 방법 수를 계산합니다.​


입력

입력의 첫 번째 줄에는 N이 입력됩니다.

다음 N 줄에는 각각 i번째 소의 위시리스트가 입력됩니다. 입력은 각 행이 1…N의 순열임을 보장합니다.

 

다음 줄에는 Q가 입력됩니다.​

마지막 Q 줄에는 각각 문자 G와 H로만 구성된 길이가 N인 품종 문자열이 입력됩니다.. 동일한 품종​ 문자열은 두 번 이상 표시되지 않습니다.​


출력

각 기호 문자열에 대해 해당 개수의 재할당 방법을 포함하는 행을 출력합니다.


예제1

입력
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


출처

USACO 2022 February Gold

역링크 공식 문제집만