LOJ3330 [WC2020]猜数游戏

题意过于神秘，就没有简述了。

首先考虑如何判断 $a_i$ 能否表示 $a_j$。如果 $a_i$ 是 $q(p = q ^ k)$ 的话，那么容易发现不超过 $k$ 次幂就一定会变成 0，这样直接暴力查表即可，时间复杂度 $O(n\log n)$ 或者 $O(n\log ^ 2n)$。否则的话，一定可以发现 $a_i$ 可以在原根下有离散对数，这样是否有次幂就可以看作是否在模意义下有倍数，即是否存在一个 $t$ 满足 $t\times \ln a_i\equiv \ln a_j\pmod {\varphi(p)}$。这个的检验显然就是判断 $\gcd(\ln a_j, \varphi(p))$ 是否整除 $\ln a_i$。

求原根时间复杂度不计，求离散对数时间复杂度 $O(n\sqrt p)$，两两判断是 $O(n ^ 2\log n)$ 的，不过 $\log$ 是 $\gcd$ 的，比较小，可以接受。

接下来考虑如何计算至少需要的次数。如果我们把 $a_i\to a_j$ 的有向边表示 $a_i$ 能表示 $a_j$ 的话，那么相当于是统计入度为 0 的点的个数。一个显然的结论是这个图是一个传递闭包，因为 $a_i\to a_j$，$a_j\to a_k$，那么 $a_i$ 一定能表示 $a_k$。

首先我们从 DAG 入手。把每个点被选的概率分开看，那么能到达他的点一定不能被选，自己一定要选，这样就可以计算概率。

不是 DAG 的情况，直接缩点后按照上面的做法计算即可。时间复杂度 $O(n\sqrt p + n ^ 2\log n)$，可以接受，比较卡常。

int BSGS(int a, int b)
{
	if (b == 1 || P == 1) return 0;
	static __gnu_pbds::gp_hash_table<int, int> H;
	if (H.empty())
	{
		int cur = 1, K = std::sqrt(P) + 1;
		for (int i = 0; i < K; ++ i, cur = (LL) cur * a % P)
			H[cur] = i;
	}
	int cur, ak, K = std::sqrt(P) + 1, x, y;
	cur = ak = qpow(a, K);
	ExGcd(b, P, x, y), x = (x % P + P) % P, cur = (LL) cur * x % P;
	for (int i = 1; i <= K; ++ i, cur = (LL) cur * ak % P)
		if (H.find(cur) != H.end()) return i * K - H[cur];
	return -1;
}

int Phi(int n)
{
	int res = n;
	for (int i = 2; i <= n / i; ++ i)
		if (n % i == 0) {
			res = res / i * (i - 1);
			while (n % i == 0) n /= i;
		}
	if (n != 1) res = res / n * (n - 1);
	return res;
}

int findrt()
{
	std::vector<int> fac;
	int phi = Phi(P), n = phi;
	for (int i = 2; i <= n / i; ++ i)
		if (n % i == 0) {
			fac.push_back(phi / i);
			while (n % i == 0) n /= i;
		}
	if (n ^ 1) fac.push_back(phi / n);
	
	auto check = [&](int x) -> bool {
		for (int p : fac)
			if (qpow(x, p) == 1) return false;
		return true;
	};
	for (int i = 2; i < phi; ++ i)
		if (check(i)) return i;
	return -1;
}

void tarjan(int x)
{
	dfn[x] = low[x] = ++ *dfn, ins[stk[++ top] = x] = true;
	for (int v : g[x])
		if (!dfn[v]) tarjan(v), chkmin(low[x], low[v]);
		else if (ins[v]) chkmin(low[x], dfn[v]);
	if (low[x] ^ dfn[x]) return;
	int cur;
	++ *bel;
	do ins[cur = stk[top --]] = false, bel[cur] = *bel, sz[*bel] ++; while (cur != x);
}

void init()
{
	std::function<int(int)> inv = [&](int i) {
		return i == 1 ? 1 : (LL) (Mod - Mod / i) * inv(Mod % i) % Mod;
	};
	pw[0] = 1;
	for (int i = 1; i < N; ++ i) adj(pw[i] = pw[i - 1] * 2 - Mod);
	for (int i = 0; i < N; ++ i) ipw[i] = inv(pw[i]);
}

int main()
{
	init();
	std::cin >> n >> P;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	int phi = Phi(P), G = findrt(), frm = 2;
	for (; P % frm; ++ frm);
	__gnu_pbds::gp_hash_table<int, int> mp;
	for (int i = 1; i <= n; ++ i)
		if (a[i] % frm) a[i] = BSGS(G, a[i]);
		else mp[a[i]] = i, pp[i] = true;
	// exit(0);
	for (int i = 1; i <= n; ++ i)
		if (pp[i]) {
			int cur = (LL) a[i] * a[i] % P;
			// std::cout << i << ' ' << a[i] << " Start\n";
			while (cur)
			{
				if (mp.find(cur) != mp.end()) g[i].push_back(mp[cur]);
				// std::cout << cur << '\n';
				cur = (LL) cur * a[i] % P;
			}
			// std::cout << "End\n";
		}
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= n; ++ j)
			if (!pp[i] && !pp[j] && i != j && a[j] % Gcd(phi, a[i]) == 0)
				g[i].push_back(j);
	for (int i = 1; i <= n; ++ i)
		if (!dfn[i]) tarjan(i);
	for (int x = 1; x <= n; ++ x)
		for (int v : g[x])
			if (bel[x] != bel[v])
				h[bel[v]].push_back(bel[x]);
	int res = 0;
	for (int x = 1; x <= *bel; ++ x)
	{
		std::sort(h[x].begin(), h[x].end()), h[x].erase(std::unique(h[x].begin(), h[x].end()), h[x].end());
		int cur = 1;
		for (int v : h[x])
			cur = (LL) cur * ipw[sz[v]] % Mod;
		res = (res + (LL) cur * (pw[sz[x]] - 1) % Mod * ipw[sz[x]]) % Mod;
	}
	res = (LL) res * pw[n] % Mod;
	std::cout << res << '\n';
	return 0;
}