「杂题记录」「WC2020」猜数游戏
给出一个长度为 \(n\) 的序列和一个正整数 \(p\)。
设 \(n\) 中的元素组成一个集合 \(A\)。
二人交互：
- 一人选出一个 \(A\) 的一个非空子集 \(S\) ，
- 另一人选出一个极小的集合 \(S' \subseteq S\)，满足：\(\forall\ x \in S, \exists \ y \in S', s.t. x=y^m \pmod{p}\),代价为 \(|S'|\).
求代价的期望 \(\times 2^{n}-1 \mod 998244353\)。
这里只是形式化的定义，不保证清晰。
\(n\le 5000\) ，\(p\) 保证是奇素数幂的形式。
分析
不难发现求期望就是在扯淡。
第一个人总共有 \(2^n-1\) 种子集的选法，每种选法等概率。那么答案就是：\({每种选法的代价和} \times (2^n-1) / (2^n-1)\) ，题目要求求出每种选法的代价和。
既然不能枚举子集，一一确定答案，就考虑算每个元素的贡献。
考虑建图，如果一个元素 \(y\), \(y^m \pmod{p}\) 能够表示 \(x\)，那么就让 \(y\) 向 \(x\) 连边。
考虑一种合法的最小子集选择方案,一定是靠近入度为 0 的一些点。换句话说，一个点 \(x\) 能被选入极小集合 \(S'\) 当且仅当，没有别的选中的点可以走到这个点 \(x\).即：这个点对答案有贡献。
考虑一个点的贡献次数，也就是有多少种选点的方案使得任意一个选中的点都不能走到这个点，设可以走到这个点的点有 \(\operatorname{cnt}\) 个，那么这个点对答案的贡献就是 \(2^{n-\operatorname{cnt}-1}\).
但是这个图是存在环的，也就是对于一个非空子集 \(S\) 来说，存在多个最优集合，从原根的角度考虑连边条件。
设 \(p\) 意义下的原根为 \(g\)，点 \(A_i \equiv g^x \pmod{p},\ \ A_j \equiv g^y\pmod{p}\) ，点 \(A_i\) 与 \(A_j\) 有边,需要满足：
\[ \exists m\in \mathbb{N},mx \equiv y \pmod{\varphi(p)} \]
由于：
"若 \(x\) 是常数，那么 \(kx\)模 \(m\)能遍历所有形如 \(k(x,m)\)的数" —— ckw,Mys.C.K.
是会形成环的，所有形如 \(k(x, m)\) 的元素之间两两有边。准确的说，每一个强连通分量都是一个团。
但是不重要，考虑每个环都可以任意定向，就是即使 \(x, y\) 能相互表示，但是强制 \(x\) 表示 \(y\) 即可，这样对答案不会造成影响，相当于强制了一种最优集合的选择方式吧。
以上是对牌爷题解里 "显然" 的几点补充，建图方式参见牌爷题解，而且建图也没啥难的。