题目描述

条形码符号由交替的**深色条（1）和浅色条（0）**组成，起始必须是深色条。每个条的宽度为若干个单位，所有条的总宽度恰好为 $n$ 个单位。

• 条形码集合 $BC(n,k,m)$：
  • 包含所有满足以下条件的符号：
    1. 由 $k$ 个条组成（深色和浅色交替）。
    2. 总宽度为 $n$ 个单位。
    3. 每个条的宽度不超过 $m$ 个单位。
  • 示例：图1中的条形码属于 $BC(7,4,3)$，但不属于 $BC(7,4,2)$（因为存在宽度为 $3$ 的条）。

0: 1000100  |  8: 1100100
1: 1000110  |  9: 1100110
2: 1001000  | 10: 1101000
3: 1001100  | 11: 1101100
4: 1001110  | 12: 1101110
5: 1011000  | 13: 1110010
6: 1011100  | 14: 1110100
7: 1100010  | 15: 1110110
Figure 2: All symbols of BC(7,4,3)

• 字典序排名：
  • 图2展示了 $BC(7,4,3)$ 的所有 $16$ 个符号，按字典序排列（左侧数字表示排名）。
  • 例如，符号 1001110 的排名是 $4$。

输入格式

程序从标准输入读取数据：

1. 第一行：三个整数 $n, k, m$（$1 \leq n,k,m \leq 33$）。
2. 第二行：一个整数 $s$（$0 \leq s \leq 100$），表示需要查询排名的符号数量。
3. 接下来 $s$ 行：每行是一个条形码符号，由 '0' 和 '1' 组成（总长度 $=n$）。

输出格式

程序向标准输出写入结果：

1. 第一行：$BC(n,k,m)$ 的符号总数。
2. 接下来的 $s$ 行：每个输入符号的排名（按字典序，从 $0$ 开始计数）。

输入样例 1

7 4 3  
5  
1001110  
1110110  
1001100  
1001110  
1000100  

输出样例 1

16  
4  
15  
3  
4  
0  

关键算法

1. 符号总数计算：
   • 动态规划统计满足条件的符号数量（深色条和浅色条交替，宽度限制为 $m$）。
2. 字典序排名：
   • 生成所有合法符号并按字典序排序，查询输入符号的索引。

示例解析

• $BC(7,4,3)$ 的符号总数：$16$。
• 符号 1001110：排名 $4$（见图2）。
• 符号 1000100：排名 $0$（字典序最小）。