P8189 [USACO22FEB] Redistributing Gifts G

Farmer John 有 $N$ 个礼物，编号为 $1 \ldots N$，准备分给他的 $N$ 头奶牛，奶牛也编号为 $1 \ldots N$（$1 \leq N \leq 18$）。每头奶牛有一个愿望清单，清单是 $N$ 个礼物的一个排列，奶牛更喜欢清单中靠前的礼物。 FJ 很懒，直接将礼物 $i$ 分配给了奶牛 $i$。现在，奶牛们聚集在一起，决定重新分配礼物，使得重新分配后，每头奶牛最终得到的礼物要么与原来相同，要么是她更喜欢的礼物。 还有一个额外的限制：一个礼物只能重新分配给与它原主人同类型的奶牛（每头奶牛要么是荷斯坦牛，要么是根西牛）。给定 $Q$（$1 \leq Q \leq \min(10^5, 2^N)$）个长度为 $N$ 的品种字符串，对于每个字符串，计算符合该字符串的重新分配方案的数量。

无

无

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