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 (1≤Q≤min(105,2N)1≤Q≤min(105,2N)) length-NN breed strings, for each one count the number of reassignments that are consistent with it.
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
In this example, for the first breed string, there are two possible reassignments:
For the second breed string, the only reassignment consistent with it is the original assignment.
Problem credits: Benjamin Qi
Farmer John 为他的 N 头编号为 1…N 的奶牛准备了 N 个同样编号为 1…N 的礼物（1≤N≤18）。每头奶牛都有一个愿望单，是所有 N 个礼物的一个排列，奶牛相比序列中较晚出现的礼物更喜欢序列中较早出现的礼物。 FJ 很懒，只是对于所有 i 将礼物 i 分配给奶牛 i。现在，奶牛们自行聚集在一起并决定重新分配礼物，使得在重新分配后，每头奶牛最终得到的是她最初得到的礼物，或者比她最初得到的礼物更喜欢的礼物。 还有一个额外的限制：如果礼物最初分配给一头奶牛，则只能将礼物重新分配给同一品种的奶牛（每头奶牛是荷斯坦牛（Holstein）或更赛牛（Guernsey）之一）。给定 Q（1≤Q≤min(105,2N)）个长为 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，奶牛 2 收到礼物 2，奶牛 3 收到礼物 3，奶牛 4 收到礼物 4。 奶牛 1 收到礼物 1，奶牛 2 收到礼物 3，奶牛 3 收到礼物 2，奶牛 4 收到礼物 4。 对于第二个品种字符串，与之对应的唯一重新分配方式即为初始的分配方式。 测试点性质： 对于 T=2,…,13，测试点 T 满足 N=T+4。 测试点 14-18 满足 N=18。 供题：Benjamin Qi
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
2