P6967: 重分礼物

---

【题目描述】

【题目描述】
Farmer John 为他的 N 头编号为 1…N 的奶牛准备了 N 个同样编号为 1…N 的礼物（1≤N≤18）。每头奶牛都有一个愿望单，是所有 N 个礼物的一个排列，奶牛相比序列中较晚出现的礼物更喜欢序列中较早出现的礼物。
FJ 很懒，只是对于所有 i 将礼物 i 分配给奶牛 i。现在，奶牛们自行聚集在一起并决定重新分配礼物，使得在重新分配后，每头奶牛最终得到的是她最初得到的礼物，或者比她最初得到的礼物更喜欢的礼物。
还有一个额外的限制：如果礼物最初分配给一头奶牛，则只能将礼物重新分配给同一品种的奶牛（每头奶牛是荷斯坦牛（Holstein）或更赛牛（Guernsey）之一）。给定 Q（1≤Q≤min(10^5,2^N)个长为 N 的品种字符串，对每个字符串计算其对应的重新分配方法数。
【输入格式】（从终端 / 标准输入读入）：
输入的第一行包含 N。
以下 N 行每行包含一头奶牛的愿望单。输入保证每行均为 1…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 收到礼物 1，奶牛 2 收到礼物 2，奶牛 3 收到礼物 3，奶牛 4 收到礼物 4。
2.奶牛 1 收到礼物 1，奶牛 2 收到礼物 3，奶牛 3 收到礼物 2，奶牛 4 收到礼物 4。
对于第二个品种字符串，与之对应的唯一重新分配方式即为初始的分配方式。
【测试点性质】：
对于 T=2,…,13，测试点 T 满足 N=T+4。
测试点 14-18 满足 N=18。

题目类型~

USACO-2022-金-2月 

咻咻~

提交答案 状态 返回