【题解】[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$。

添加新评论