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\) 中的质因子已经选过的价值乘积之和。
转移为:
其中 \(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\) 步到达的点,则:
记 \(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)\),有:
两侧同时除以 \(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)}\),可得:
记 \(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\) 满足:
那么有:
\[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\) 的环长,那么答案的式子可以改写为:
现在的问题是计算 \(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