【题解】[WC2020] 猜数游戏

[WC2020] 猜数游戏

给定长度为 $n$ 的序列 $a_i$，元素两两不相等，等概率随机选一个非空子集 $b_i$。有另一人知道 $a$ 来猜测 $b$，每次可以询问一个 $a_k$，若在 $b$ 中无此数字，则告知“无”，否则告知 $b$ 中所有满足 $a_k^m \bmod p$ 的数（$m$ 为任意正整数）
现每次一定用最优方法猜测，问猜完 $b$ 所有数字的期望次数 $\times (2^n-1)$
$n \le 5000,p \le 10^{8}$，$p$ 为素数或 $q^k$ （$q$ 是素数，$k$ 为一正整数）

$\texttt{Solution}$

若询问 $a_i$ 可以知道 $a_j$，则在 $a_i\ \texttt{->}\ a_j$ 连一条边。不难发现在这张图上，强连通块中随意定向，再令点 $x$ 的入度为 $deg[x]$，则 $x$ 对答案的贡献是 $2^{n - deg[x] - 1}$，可以理解为所有前驱都不能选，自己必须选的方案数。

首先考虑 $p$ 是素数的情况，令其原根为 $g$，有任意 $a_i$ 可以表示为 $g^{k_i}$ 的形式。

则现在若 $a_i$ 可以知道 $a_j$，等价于存在 $x$ 使 $x \times k_i \equiv k_j(\bmod \varphi(p))$

可以发现对于一个数字 $a_i$，他可以遍历到的集合和步长是 $\gcd(k_i,\varphi(p))$ 的集合相等。因此我们现在可以不用求每个 $k_i$，转而求每个 $\gcd(k_i,\varphi(p))$。可以发现这样一个步长为 $\gcd(k_i,\varphi(p))$ 的集合，跳 $\dfrac{\varphi(p)}{\gcd(k_i,\varphi(p))}$ 步就会回到原点，也就是:
$$\gcd(k_i,\varphi(p)) \times \dfrac{\varphi(p)}{\gcd(k_i,\varphi(p))} \equiv 0 (\bmod \varphi(p))$$

令 $\dfrac{\varphi(p)}{\gcd(k_i,\varphi(p))}=m$，则可以写作：

$$ a_i^m \equiv 1 (\bmod p)$$

可以发现 $m$ 恰好是最小的满足以上条件的数，正好是 $a_i$ 在模 $p$ 意义下的阶。所以只要我们求出每个 $a_i$ 的阶 $m_i$，即可求出每个 $\gcd(k_i,\varphi(p))$。至于求阶，发现他一定是 $\varphi(p)$ 的约数，在本题中暴力枚举约数来求即可。

现在我们令 $f(a_i)=\gcd(k_i,\varphi(p))$，则可以发现若从 $a_i$ 可以得到 $a_j$，只需满足条件 $f(a_i)\ |\ f(a_j)$。

若 $p=q^k$，则若 $\gcd(a_i,p) \ne 1$，那么一定有 $a_i=t\times q$，$a_i^k$ 及之后值均为 $0$，暴力连边即可。

需要单独考虑 $a_i=1$ 的情况，可以发现任意满足 $\gcd(a_j,p)=1$ 的 $a_j$，一定可以得到 $a_i$，所以令 $\gcd(a_j,p) \ne 1$ 的个数为 $z$，则 $a_i$ 对答案的贡献为 $2^z$。