SP518 ZZPERM - Zig-Zag Permutation

我们在这里讨论的字符串，只由小写字母 'a' 到 'j' 组成，并按照字母顺序 'a' < 'b' < ... < 'j' 排列。你的任务是编写一个程序，用于从给定的字母集合中生成几乎所有的锯齿形单词（即锯齿形排列）。所谓锯齿形单词 $W = W(1)W(2)...W(n)$，当且仅当 $n = 1$ 或对于所有的奇数位置 $0 < i < n$ 和所有的偶数位置 $0 < j < n$ 满足 $W(i) > W(i+1)$ 且 $W(j) < W(j+1)$，或者对于所有的偶数位置 $0 < i < n$ 和所有的奇数位置 $0 < j < n$ 满足 $W(i) > W(i+1)$ 且 $W(j) < W(j+1)$。例如：“aabcc”不是锯齿形的，而“acacb”是锯齿形的，“cac”也是锯齿形的，“abababc”则不是锯齿形的。 考虑字典序中所有可能的锯齿形排列，你可以根据排列的顺序为它们分配一个序列号（排名）。例如：单词“aabcc”会生成如下序列： 1 对应“acacb”, 2 对应“acbca”, 3 对应“bacac”, 4 对应“bcaca”, 5 对应“cabac”, 6 对应“cacab”。

输入文件包含多个测试用例。每个测试用例包括一个不超过 64 个字母的单词 $W$，以及一个正整数 $D$。单词中的字母按照递增顺序给出。输入以 EOF 结束。

对于输入文件中的每个测试用例，输出文件必须列出所有锯齿形排列中序列号能被 $D$ 整除的排列，输出按字典序递增排列——每行输出一个单词。在这些排列的下面一行，打印单词 $W$ 的所有锯齿形排列的总数。每个测试用例的输出不会超过 365 行。在每个测试用例输出后加一个空行。

- 单词的长度 $|W| \leq 64$ - 数字 $1 \leq D \leq 10^9$ **本翻译由 AI 自动生成**