Redistributing Gifts

题目描述

农夫约翰有 $N$ 份礼物，编号为 $1\ldots N$，要送给他的 $N$ 头奶牛，奶牛也编号为 $1\ldots 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 组成。任意品种字符串不会出现超过一次。

输出格式

对每个品种字符串，输出与之相容的重新分配方案数量，每个结果占一行。

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

提示

在这个例子中，对于第一个品种字符串，有两种可能的重新分配： 原始分配：奶牛 $1$ 获得礼物 $1$，奶牛 $2$ 获得礼物 $2$，奶牛 $3$ 获得礼物 $3$，奶牛 $4$ 获得礼物 $4$。 奶牛 $1$ 获得礼物 $1$，奶牛 $2$ 获得礼物 $3$，奶牛 $3$ 获得礼物 $2$，奶牛 $4$ 获得礼物 $4$。 对于第二个品种字符串，与之相容的唯一重新分配是原始分配。 计分： 对于 $T = 2, \ldots, 13$，测试点 $T$ 满足 $N = T + 4$。 测试点 14-18 满足 $N = 18$。 题目署名：Benjamin Qi

标签: USACO|2022|Gold

来源

USACO|2022|Gold