#P8189. [USACO22FEB] Redistributing Gifts G

[USACO22FEB] Redistributing Gifts G

题目描述

Farmer John has NN gifts labeled 1N1…N for his NN cows, also labeled 1N1…N (1N18)(1≤N≤18). Each cow has a wishlist, which is a permutation of all NN gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.

FJ was lazy and just assigned gift ii to cow ii for all ii. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.

There is also an additional constraint: a gift may only be reassigned to a cow if it was originally assigned to a cow of the same type (each cow is either a Holstein or a Guernsey). Given QQ (1Qmin(105,2N))(1≤Q≤min(10^5,2^N)) length-NN breed strings, for each one count the number of reassignments that are consistent with it.

输入格式

The first line contains NN. The next NN lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of 1N1…N.

The next line contains QQ.

The final QQ lines each contain a breed string, each NN characters long and consisting only of the characters G and H. No breed string occurs more than once.

输出格式

For each breed string, print the number of reassignments that are consistent with it on a new line.

题目大意

题目描述

Farmer John 有 NN 个礼物,编号为 1N1 \ldots N,准备分给他的 NN 头奶牛,奶牛也编号为 1N1 \ldots N1N181 \leq N \leq 18)。每头奶牛有一个愿望清单,清单是 NN 个礼物的一个排列,奶牛更喜欢清单中靠前的礼物。

FJ 很懒,直接将礼物 ii 分配给了奶牛 ii。现在,奶牛们聚集在一起,决定重新分配礼物,使得重新分配后,每头奶牛最终得到的礼物要么与原来相同,要么是她更喜欢的礼物。

还有一个额外的限制:一个礼物只能重新分配给与它原主人同类型的奶牛(每头奶牛要么是荷斯坦牛,要么是根西牛)。给定 QQ1Qmin(105,2N)1 \leq Q \leq \min(10^5, 2^N))个长度为 NN 的品种字符串,对于每个字符串,计算符合该字符串的重新分配方案的数量。

输入格式

第一行包含 NN
接下来的 NN 行,每行包含一头奶牛的愿望清单。保证每行是 1N1 \ldots N 的一个排列。
接下来一行包含 QQ
最后的 QQ 行,每行包含一个品种字符串,长度为 NN,仅由字符 GH 组成。每个品种字符串只出现一次。

输出格式

对于每个品种字符串,输出一行,表示符合该字符串的重新分配方案的数量。

样例解释

在这个例子中,对于第一个品种字符串,有两种可能的重新分配方案:

  1. 原始分配:奶牛 11 得到礼物 11,奶牛 22 得到礼物 22,奶牛 33 得到礼物 33,奶牛 44 得到礼物 44
  2. 奶牛 11 得到礼物 11,奶牛 22 得到礼物 33,奶牛 33 得到礼物 22,奶牛 44 得到礼物 44

数据范围

  • 对于 T=2,,13T = 2, \cdots ,13,测试用例 TT 满足 N=T+4N = T + 4
  • 测试用例 14-18 满足 N=18N = 18

输入数据 1

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG

输出数据 1

2
1
1
2
2

提示

【样例解释】

In this example, for the first breed string, there are two possible reassignments:

  • The original assignment: cow 11 receives gift 11, cow 22 receives gift 22, cow 33 receives gift 33, and cow 44 receives gift 44.
  • Cow 11 receives gift 11, cow 22 receives gift 33, cow 33 receives gift 22, and cow 44 receives gift 44.

【数据范围】

  • For T=2,,13T=2,\cdots ,13, test case T satisfies N=T+4N=T+4.
  • Test cases 14-18 satisfy N=18N=18.