#CW79. 礼物交换(gift)

    ID: 309 传统题 文件IO:gift 1000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>成外联盟2026动态规划状态压缩DP

礼物交换(gift)

题目描述

有 NN 头奶牛和 NN 种礼物,编号均为 1,2,…,N1, 2, \ldots, N。第 ii 头奶牛给出一个长度为 NN 的排列作为愿望表;礼物在表中越靠前,奶牛越喜欢。最初奶牛 ii 得到礼物 ii。

重新分配后,每头奶牛必须得到原礼物,或得到愿望表中排在原礼物之前的礼物;每种礼物恰好分配给一头奶牛。每头奶牛还标记为 H 或 G。查询给出一个长度为 NN 的字符串,表示各奶牛标记。标记为 H 的奶牛只能在彼此之间交换礼物,标记为 G 的奶牛也只能在彼此之间交换,禁止跨组交换。请输出合法方案数。

输入格式

从 gift.in 文件中读入。

第一行是 NN,满足 1≤N≤181 \le N \le 18。接下来 NN 行是愿望表排列。下一行是 QQ,满足 1≤Q≤min⁡(105,2N)1 \le Q \le \min(10^5, 2^N)。接下来 QQ 行各有一个长度为 NN、只含 G 和 H 的字符串,且字符串互不相同。

输出格式

向 gift.out 文件中输出。

对每个查询输出一行合法重新分配方案数。

样例 1 输入

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG

样例 1 输出

2
1
1
2
2

样例 1 解释

奶牛 1 最喜欢礼物 1,因此它只能保留礼物 1。奶牛 2 可以接受礼物 1, 3, 2,奶牛 3 可以接受礼物 1, 2, 3。由于礼物 1 已被奶牛 1 占用,奶牛 2 和奶牛 3 必须分配礼物 2 和礼物 3,奶牛 4 也就只能保留礼物 4。

暂不考虑标记时,恰好有两种满足喜好要求的分配:奶牛 1, 2, 3, 4 依次得到礼物 (1,2,3,4)(1, 2, 3, 4),或依次得到礼物 (1,3,2,4)(1, 3, 2, 4)。前者始终合法;后者交换了奶牛 2 和奶牛 3 的礼物,只有这两头奶牛的标记相同时才合法。

因此,查询 HHHH、HGGG、GHHG 都有 2 种方案;查询 HHGG、GHGH 中奶牛 2 与奶牛 3 的标记不同,只有保留原礼物的 1 种方案。按查询顺序输出即为 2, 1, 1, 2, 2。

数据范围

所有输入数据均为整数。每行愿望表都是 1,2,…,N1, 2, \ldots, N 的完整排列。

本题采用子任务捆绑计分:通过一个子任务的全部测试点,才能获得该子任务的分数。

子任务 分值 测试点 附加条件
1 20 1∼41 \sim 4 N≤8N \le 8
2 25 5∼95 \sim 9 N≤12N \le 12
3 10∼1410 \sim 14 Q≤1000Q \le 1000
4 30 15∼2015 \sim 20 无额外限制