P14502 [NCPC 2025] Hidden Permutation

当对一副牌反复应用某种固定的洗牌方式时，这副牌最终会回到其原始顺序。将洗牌方式需要应用的次数称为该洗牌方式下这副牌的 **周期（period）**。在本题中，我们考虑的是逆问题：我们并非给定洗牌方式并求其周期，而是给定每一种可能的周期，各有多少副牌具有该周期。你的任务是构造任意一个与这些信息一致的洗牌方式。 形式化地，存在一个隐藏排列 $f = (f_1, f_2, \dots, f_N)$，其中 $N$ 是给定的正整数。排列是一个包含 $1$ 到 $N$ 的数字且每个数字恰好出现一次的列表。令 $x = x_1x_2\dots x_N$ 为一个二进制字符串。我们定义 $f(x)$（即对 $x$ 应用 $f$）为新的二进制字符串 $x_{f_1}x_{f_2}\dots x_{f_N}$；并且定义 $x$ 的 **周期** 为最小的正整数 $p$，使得： $$ \underbrace{f(f(\cdots f(x)\cdots))}_{p\ \text{次}} = x. $$ 可以证明，对于任意排列 $f$ 与任意同长度的二进制字符串 $x$，$x$ 的周期一定存在。换句话说，如果你对 $x$ 应用足够多次 $f$，最终总会回到 $x$。 你将得到数字 $N$，以及对每个可能的周期 $p$，有多少个（在全部 $2^N$ 个可能的二进制字符串中）二进制字符串的周期为 $p$。你的任务是找到一个与这些信息一致的排列 $f$，或者得出不存在这样的排列。

输入包含： - 一行两个整数 $N$, $K$（$2 \le N \le 100$, $1 \le K \le 1000$），表示排列的长度以及可能的周期数量。 - 一行包含 $K$ 个整数 $p_1, p_2, \dots, p_K$（$1 \le p_i \le 10^9$）。这些是对于隐藏排列而言，长度为 $N$ 的二进制字符串所有可能出现的周期。所有 $p_i$ 互不相同，且已按升序排列。 - 一行包含 $K$ 个整数 $m_1, m_2, \dots, m_K$（$1 \le m_i \le 2^{100}$）。其中 $m_i$ 表示周期为 $p_i$ 的二进制字符串数量。 注意：数字 $m_i$ 的大小可能非常大！

如果不存在任何排列 $f$ 能与给定信息对应，则输出 `impossible`。 否则输出一行，包含 $N$ 个整数 $f_1, f_2, \dots, f_N$，即你选择的排列。排列必须包含 $1$ 到 $N$ 且每个数字恰好出现一次。若存在多个合法解，你可以输出任意一个。

在第二个样例中，输入几乎对应于排列 $(2,3,4,\dots,91,1)$。唯一的错误是输入中最后一个数字的末位应为 $0$ 而不是 $1$。 在第三个样例中，全部 $4$ 个二进制字符串的周期都是 $1$，因此恒等排列 $(1,2)$ 是一个合法答案。 翻译由 ChatGPT-5 完成