ARC182 题解

标签：right frac ARC182 题解 bmod gcd left equiv

A - Chmax Rush!

发现一个数能向哪边覆盖只由再他之后操作且 \(v\) 比他大的操作决定。
所以扫一遍确定方向之后乘起来就好。

B - |{floor(A_i/2^k)}|

首先不难发现 \(< 2_{k - 1}\) 的元素是无用的，因为它们会由 \(\ge 2^{k - 1}\) 的元素除以 2 的幂得到。

先想上界。对于 \(0 \le x < k\)，处于 \([2^x, 2^{x + 1})\) 的元素至多有 \(\min(n, 2^x)\) 个，所以上界就是 \(\sum_{0 \le x < k} \min(n, 2^x)\)。

再想怎么达到上界。可以简单地构造 \(a_i = 2^{k - 1} + \operatorname{rev}(i)\)，其中 \(\operatorname{rev}(i)\) 表示 \(i\) 在二进制下表示下数位翻转后的数。

C - Sum of Number of Divisors of Product

先考虑确定序列 \(a_{i, \cdots, n}\) 后如何算贡献：

\[ans = \prod_{p \in \mathbb{prime}} \left(1 + \sum_{i = 1}^n cnt_{a_i, p}\right) \]

其中 \(cnt_{x, p}\) 表示 \(p\) 这个质因子在 \(x\) 中的出现次数。

考虑式子的组合意义，就是每个质因子都有 \(n\) 个物品，第 \(i\) 个的价值为 \(cnt_{a_i, p}\)，每个质因子至多选一个物品，求所有选择方案的物品价值乘积之和。

然后对着组合意义写 DP 式子：记 \(f_{i, S}\) 表示考虑了前 \(i\) 个位置，\(S\) 中的质因子已经选过的价值乘积之和。
转移为：

\[f_{i, S} \times \sum_{j = 1}^m val_{j, T} \rightarrow f_{i + 1, S \cup T} \]

其中 \(val_{j, T}\) 表示填 \(j\) 时考虑 \(T\) 中的质因子的贡献。

发现可以写成矩阵乘法的形式，所以时间复杂度 \(O\left(8^{\pi(m)} \log n\right)\)。

D - Increment Decrement Again

取模很烦人，考虑先把取模干掉。
然后对于相邻两项的限制就变成了 \(a_i \neq a_{i + 1} \and \lvert a_i - a_{i + 1} \rvert < m\)。
如果我们把序列调整成不降的，那么确定了首项就能确定整个序列。
可以将 \(A\) 调整成满足条件的不降的序列。
如果我们将 \(B\) 类似地调整成 \(B'\)，问题就变成了确定 \(B'_1\) 使得 $\sum_{i = 1}^n \lvert B'_i - A_i \rvert $ 最小。
如果记 \(B'_1 = B_1\) 的 \(B'\) 序列为 \(C\)，则 \(B'_i\) 都可以表示成 \(B'_i = C_i + k \times m\) 的形式，那么我们就是让 \(\sum_{i = 1}^n \lvert C_i - A_i + k \times m \rvert\) 最小。
如果不强制是 \(k \times m\) 的话就是取中位数，否则就中位数附近的几个 \(m\) 的倍数算一下即可。

F - Graph of Mod of Linear

基本上是翻译了一下官方题解，加入了一些自己的思考。

对每组询问分别考虑。

如果把边视为有向边，则生成的图是一棵内向基环树，连通块数与环的数量是相等的。
首先特判掉 \(A = 1\) 和 \(A = 0\) 的情况。\(A = 0\) 时答案为 \(1\)，因为连成了一个菊花；\(A = 1\) 时答案为 \(\gcd(N, B)\)，因为连成了 \(\gcd(N, B)\) 个环。
发现如果 \(A \perp N\)，则 \(Ax + B\) 互不相等，连成的是若干个环，所以考虑按 \(A\) 与 \(N\) 是否互质分类讨论。

Case1: \(\gcd(A, N) > 1\)

我们想知道的是环上的点有哪些。考虑如果每个点都沿着出边跳 \(N\) 步，最后一定跳到环上且环上的点都会被跳到。
所以记 \(f^{N}(x)\) 表示从点 \(x\) 跳 \(N\) 步到达的点，则：

\[\begin{aligned} f^{N}(x) & \equiv A(\cdots(A(Ax + B) + B) + \cdots) + B \\ & \equiv A^N x + \sum_{i = 0}^{N - 1} B A^{i} \equiv A^N x + B \frac{A^N - 1}{A - 1} \pmod N \end{aligned}\]

记 \(d = \gcd(N, A^N)\)，发现 \(f^N(x + 1) - f^N(x) \equiv A^N \equiv 0 \pmod d\)。
这就是在说，对于所有在环上的点，它们都是与 \(f^N(0) = B\frac{A^N - 1}{A - 1}\) 模 \(d\) 同余的。
所以考虑把这些点单独拉出来，转化到 \(\gcd(A, N) = 1\) 的情况。
考虑对于环上的一个点 \(u = dk_1 + f^N(0)\) 和它连向的点 \(v = dk_2 + f^N(0)\)，有：

\[\begin{aligned} dk_2 + f^N(0) &\equiv A(dk_1 + f^N(0)) + B \\ dk_2 &\equiv Adk_1 + (A - 1)f^N(0) + B \\ dk_2 &\equiv Adk_1 + B A^N \pmod N \end{aligned}\]

两侧同时除以 \(d\)，可得：

\[\begin{aligned} k_2 &\equiv Ak_1 + B \frac{A^n}{d} \quad \left(\bmod{\frac{N}{d}} \right) \end{aligned}\]

问题就从 \((N, A, B)\) 转化为了 \((\frac{N}{d}, A \bmod \frac{N}{d}, B \cdot \frac{A^n}{d} \bmod{\frac{N}{d}})\)。

Case2: \(\gcd(A, N) = 1\)

连通块数与环的数量相等，考虑怎么数环的数量。
可以将每个点的权值设为它所在环的长度的倒数，这样对于一个环长为 \(k\) 的环，它的贡献为 \(k \cdot \frac{1}{k} = 1\)，求和即为环的数量。

对于点 \(x\)，如果它在 \(K\) 步后回到 \(x\)，那么有：

\[\begin{aligned} A^K x + B \frac{A^K - 1}{A - 1} & \equiv x \pmod N \\ \left(A^K - 1 \right) \left( x + \frac{B}{A - 1} \right) & \equiv 0 \pmod N \\ \end{aligned}\]

两边同时除以 \(\gcd\left(x + \dfrac{B}{A - 1}, N \right) = \dfrac{\gcd\big(x(A - 1) +B, N(A - 1)\big)}{A - 1}\)，得：

\[\begin{aligned} A^K \equiv 1 \quad \left( \bmod \frac{N(A - 1)}{\gcd\big(x(A - 1) +B, N(A - 1)\big)} \right) \end{aligned}\]

化简一下。记 \(G = \gcd(A - 1, B)\)，则 \(A' = \frac{A - 1}{G}\)，\(B' = \frac{B}{G}\)，可得到：

\[A^K \equiv 1 \quad \left( \bmod \frac{N A'}{\gcd(xA' + B', NA')} \right) \]

此时有 \(xA' + B \perp A'\)，所以模数分母上的 \(\gcd\) 中不含 \(A'\) 的因子，可以全部除掉。
所以记 \(N' = \dfrac{N}{\gcd(A'^N, N)}\)，可得：

\[A^K \equiv 1 \quad \left( \bmod \frac{N A'}{\gcd(xA' + B', N')} \right) \]

记 \(y = xA' + B' \bmod N'\)，由于 \(A' \perp N'\)，所以对于 \(x \in [0, N') \cap \mathbb Z\)，\(y\) 互不相同且取遍 \([0, N') \cap \mathbb Z\)，那么对于 \(x \in [0, N) \cap \mathbb Z\)，每个不同的 \(y\) 都恰好取到过 \(\frac{N}{N'}\) 次。
记 \(C_y\) 表示 满足 \(y = xA' + B' \bmod N'\) 的点 \(x\) 的环长，也即最小的 \(k\) 满足：

\[A^K \equiv 1 \quad \left( \bmod \dfrac{N A'}{\gcd(y, N')} \right) \]

那么有：

\[ans = \frac{N}{N'} \sum_{y = 0}^{N' - 1} \frac{1}{C_y} \]

发现对于 \(\gcd(y, N')\) 相同的 \(y\) 有相同的 \(C_y\)，所以考虑将枚举 \(y\) 改为枚举 \(\gcd(y, N')\)。
记 \(n = \gcd(y, N')\)，则对应的 \(y\) 有 \(\varphi\left(\dfrac{N'}{n}\right)\) 个，因为除掉 \(n\) 之后要互质。
更改 \(C_n\) 的定义为 满足 \(y = xA' + B' \bmod N', \gcd(y, N') = n\) 的点 \(x\) 的环长，那么答案的式子可以改写为：

\[ans = \frac{N}{N'} \sum_{n \mid N'} \frac{1}{C_n} \varphi\left(\dfrac{N'}{n_1}\right) \]

现在的问题是计算 \(C_n\)。
有以下性质：

• \(C_1\) 为 \(\varphi(NA')\) 的因数。
• 对于 \(n_1 \mid N'\)，\(n_2 \mid N'\)，如果 \(n_1 \mid n_2\)，那么 \(C_{n_2} \mid C_{n_1}\)。

第一个性质是欧拉定理，第二个性质是考虑：

\[\begin{aligned} A^{C_{n_1}} \equiv 1 \quad \left( \bmod \frac{N'A}{n_1} \right) \\ A^{C_{n_2}} \equiv 1 \quad \left( \bmod \frac{N'A}{n_2} \right) \end{aligned}\]

因为 \(n_1 \mod n_2\)，那么 \(\frac{N'A}{n_2} \mid \frac{N'A}{n_1}\)，所以：

\[A^{C_{n_1}} \equiv 1 \quad \left( \bmod \frac{N'A}{n_2} \right) \]

所以 \(C_{n_2} \mid C_{n_1}\)。

有了这两个性质就可以通过记搜把 \(C_n\) 搜出来。
具体来讲：搜索时记录二元组 \((n, C)\) 表示当前的 \(n\) 和上一次的 \(C\)，枚举 \(\varphi(NA')\) 的质因子，不断尝试将他们除掉，可以用快速幂判定，算出当前的 \(C\) 后枚举 \(N'\) 的质因子 \(p\)，递归到 \((n \cdot p, C)\)。

时间复杂度不怎么会算，感觉大概是什么 \(O\big(q \omega(V) d(n)\big)\)，其中 \(V = 10^{12}\)，\(d(n)\) 表示 \(n\) 的因子个数，\(\omega(n)\) 表示 \(n\) 的质因子个数。

代码

标签：right,frac,ARC182,题解,bmod,gcd,left,equiv
From： https://www.cnblogs.com/definieren/p/18354900