레이팅 미적용농부 존은 \(N\)마리의 소(\(1\le N\le 18\), 소들은 \(1\ldots N\)으로 번호가 매겨져 있다)에게 줄 \(1\ldots N\)으로 번호가 매겨진 \(N\)개의 선물을 가지고 있다. 각 소는 위시리스트를 가지고 있는데, 이는 \(N\)개 선물 전체의 순열로, 리스트에서 앞에 나오는 선물을 뒤에 나오는 선물보다 더 선호한다는 뜻이다.
농부 존은 게을러서 모든 \(i\)에 대해 선물 \(i\)를 소 \(i\)에게 그냥 배정했다. 이제 소들이 모여서 선물을 재배정하기로 했는데, 재배정 후 모든 소는 원래 받은 선물과 같은 선물을 받거나, 원래 배정받은 선물보다 더 선호하는 선물을 받아야 한다.
추가 제약이 하나 더 있다. 어떤 선물은 원래 그 선물이 배정되었던 소와 같은 품종의 소에게만 재배정될 수 있다(각 소는 홀스타인이거나 건지이다). 길이 \(N\)의 품종 문자열 \(Q\)개(\(1\le Q\le \min(10^5,2^N)\))가 주어질 때, 각 문자열에 대해 그 문자열과 일치하는 재배정의 수를 세어라.
Problem credits: Benjamin Qi
채점 방식
- \(T = 2, \ldots, 13\)에 대해, 테스트 케이스 \(T\)는 \(N = T + 4\)를 만족한다.
- 테스트 케이스 14-18은 \(N = 18\)을 만족한다.
Problem credits: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에는 각 소의 선호 리스트가 한 줄에 하나씩 주어진다. 각 줄은 \(1\dots N\)의 순열임이 보장된다.
다음 줄에 \(Q\)가 주어진다.
마지막 \(Q\)개의 줄에는 품종 문자열이 한 줄에 하나씩 주어진다. 각 문자열은 길이가 \(N\)이고 문자 G와 H로만 이루어져 있다. 같은 품종 문자열이 두 번 이상 등장하지 않는다.
각 품종 문자열에 대해, 그 문자열과 일치하는 재배정의 수를 한 줄에 하나씩 출력한다.
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG2
1
1
2
2In this example, for the first breed string, there are two possible reassignments:
- The original assignment: cow \(1\) receives gift \(1\), cow \(2\) receives gift \(2\), cow \(3\) receives gift \(3\), and cow \(4\) receives gift \(4\).
- Cow \(1\) receives gift \(1\), cow \(2\) receives gift \(3\), cow \(3\) receives gift \(2\), and cow \(4\) receives gift \(4\).
For the second breed string, the only reassignment consistent with it is the
original assignment.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > February > Gold