06690. USACO·礼物再分配 未做

Farmer John 为他的 $N$ 头编号为 $1\dots N$ 的奶牛准备了 $N$ 个同样编号为 $1\dots N$ 的礼物（$1\le N\le 18$）。每头奶牛都有一个愿望单，是所有 $N$ 个礼物的一个排列，奶牛相比序列中较晚出现的礼物更喜欢序列中较早出现的礼物。

FJ 很懒，只是对于所有 $i$ 将礼物 $i$ 分配给奶牛 $i$。现在，奶牛们自行聚集在一起并决定重新分配礼物，使得在重新分配后，每头奶牛最终得到的是她最初得到的礼物，或者比她最初得到的礼物更喜欢的礼物。

还有一个额外的限制：如果礼物最初分配给一头奶牛，则只能将礼物重新分配给同一品种的奶牛（每头奶牛是荷斯坦牛（Holstein）或更赛牛（Guernsey）之一）。给定 $Q$（$1\le Q\le \min (10^5,2^N)$）个长为 $N$ 的品种字符串，对每个字符串计算其对应的重新分配方法数。

输入的第一行包含 $N$。

以下 $N$ 行每行包含一头奶牛的愿望单。输入保证每行均为 $1\dots N$ 的一个排列。

以下一行包含 $Q$。

最后 $Q$ 行每行包含一个品种字符串，长度为 $N$ 且仅由字符 G 和 H 组成。没有品种字符串会出现超过一次。

对于每一个品种字符串，输出一行，包含其对应的重新分配方法数。

【样例解释】

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

• 初始的分配方式：奶牛 $1$ 收到礼物 $1$，奶牛 $2$ 收到礼物 $2$，奶牛 $3$ 收到礼物 $3$，奶牛 $4$ 收到礼物 $4$。

• 奶牛 $1$ 收到礼物 $1$，奶牛 $2$ 收到礼物 $3$，奶牛 $3$ 收到礼物 $2$，奶牛 $4$ 收到礼物 $4$。

对于第二个品种字符串，与之对应的唯一重新分配方式即为初始的分配方式。

• 测试点 14-18 满足 $N=18$。

【数据规模与约定】

• 对于 $T=2,\dots ,13$，测试点 $T$ 满足 $N=T+4$。

• 测试点 14-18 满足 $N=18$。

供题：Benjamin Qi