自动搬运

查看原文

来自洛谷，原作者为

	Mivik AFO

搬运于2025-08-24 22:36:25，当前版本为作者最后更新于2022-02-03 11:21:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Subtask 1

给暴力分是中华民族的优秀传统美德。

Subtask 2

我们注意到这个子任务给了很多分，暗示着出题人认为会了求单点就差不多会做了（嗯嗯）。

保留题目中 1 开始的下标机制，我们发现洗一次牌本质上就是进行一次

$$k\rightarrow 2k\pmod{2^n+1}$$

的置换（记为 $P$）。而题目中的 $f(n)$ 实际上就是在对 $P^0,P^1,P^2,\dots,P^{n-1}$ 这些置换的不动点个数求和。

不妨先来研究一下这个置换的环。首先有个显然的观察：环长最大是 $2n$。因为对于任何整数 $t$（$1\le t\le\left(2^n+1\right)$），我们有

$$\begin{aligned} &2^{2n}t\\ =&\left(2^{2n}-1\right)t+t\\ =&\left(2^n-1\right)\left(2^n+1\right)t+t\\ =&t\pmod{2^n+1} \end{aligned} $$

我们想要求出长度为 $k$ 的环有多少个，可直接切入似乎会没有什么思路。我们考虑计算所在环长度为 $k$ 的约数的数的个数 $B_k$，然后就可以莫比乌斯反演得到所在环长度为 $k$ 的数的个数 $A_k$。

我们发现，对于一个数 $t$，它在一个长度为 $k$ 的约数的环内，当且仅当

$$\begin{aligned} 2^kt&\equiv t\pmod{2^n+1}\\ \left(2^k-1\right)t&\equiv 0\pmod{2^n+1} \end{aligned} $$

即

$$\begin{aligned} (2^n+1)&\mid \left((2^k-1)t\right)\\ \frac{2^n+1}{\left(2^n+1,2^k-1\right)}&\mid t \end{aligned} $$

$\left(2^n+1,2^k-1\right)$？这不难让我们想起一个定理：

定理一：对于 $n,m,a\in\Z^+$，有

$$\left(a^n-1,a^m-1\right)=a^{(n,m)}-1$$

关于这个定理的一个（甚至更通用的证明）可以看 这里。

可是上面的是 $\left(2^n+1,2^k-1\right)$，看起来似乎没什么联系啊？

我们不妨改写为

$$\left(2^n+1,2^k-1\right)=\left(\frac{2^{2n}-1}{2^n-1},2^k-1\right) $$

然后我们知道

定理二：对于 $p,q,k\in\Z^+,(p,q)=1$，有

$$(k,p)=\frac{(k,pq)}{(k,q)}$$

这个挺显然的。由于 $(2^n-1,2^n+1)=(2^n-1,2)=1$，于是就有

$$\begin{aligned} &\left(2^n+1,2^k-1\right)\\ =&\left(\frac{2^{2n}-1}{2^n-1},2^k-1\right)\\ =&\frac{\left(2^{2n}-1,2^k-1\right)}{\left(2^n-1,2^k-1\right)}\\ =&\frac{2^{(2n,k)}-1}{2^{(n,k)}-1} \end{aligned} $$

我们分两种情况讨论：

$\frac k{(n,k)}$ 为奇数

也就是说 $(k,2n)=(k,n)$，那么

$$\begin{aligned} \left(2^{2n}-1,2^k-1\right)=\left(2^n-1,2^k-1\right)&=2^{(n,k)}-1\\ \left(2^n+1,2^k-1\right)&=1 \end{aligned} $$

条件转化为

$$\left(2^n+1\right)\mid t$$

由于 $1\le t\le 2^n$，显然有 $B_k=0$。

$\frac k{(n,k)}$ 为偶数

那么 $(k,2n)=2(k,n)$，则有

$$\begin{aligned} \left(2^{2n}-1,2^k-1\right)&=2^{2(n,k)}-1\\ \left(2^n-1,2^k-1\right)&=2^{(n,k)}-1\\ \left(2^n+1,2^k-1\right)&=2^{(n,k)}+1 \end{aligned} $$

条件转化为

$$\frac{2^n+1}{2^{(n,k)}+1}\mid t$$

由于 $1\le t\le 2^n$，则 $B_k=2^{(n,k)}$。

---

总结一下

$$B_k= \begin{cases} 2^{(n,k)},&2\mid\frac k{(n,k)}\\ 0,&\text{otherwise.} \end{cases} $$

记 $n=2^qp$（$p$ 为奇数），那么

$$2\mid\frac k{(n,k)}\iff 2^{q+1}\mid k$$

套用反演可得

$$A_k=\sum_{d|k}\mu(d)B_{k/d}$$

我们考虑到原题要求的 $P^0,P^1,P^2,\dots,P^{n-1}$ 的不动点个数之和似乎并不是非常的 canonical：最长的环有 $2n$ 长怎么只求前 $n$ 个？我们不妨先求出 $P^0,P^1,P^2,\dots,P^{2n-1}$ 的不动点个数之和，记之为 $g(n)$。

首先我们观察到环长必须得是 $(2n)$ 的约数。由于一个长度为 $w$ 的环对 $f(n)$ 的贡献为 $\left(\frac{2n}w\right)$，对 $g(n)$ 的贡献为

$$\left\lfloor\frac nw\right\rfloor=\frac12\left(1+\frac{2n}w\right) $$

于是就有 $f(n)=\frac12\left(g(n)+2^n\right)$。我们只需要求出 $g(n)$ 即可。

整理式子之前现有一个小定理：

定理三：

$$\sum_{k=1}^n\mu(k)\left\lfloor\frac nk\right\rfloor=1 $$

证明：

$$\begin{aligned} &\sum_{k=1}^n\mu(k)\left\lfloor\frac nk\right\rfloor\\ =&\sum_{k=1}^n\mu(k)\sum_{k|d,d\le n}1\\ =&\sum_{d=1}^n\sum_{k|d}\mu(k)\\ =&\sum_{d=1}^n\left[d=1\right]\\ =&1 \end{aligned} $$

于是开始整理式子：

$$\begin{aligned} g(n)&=\sum_{k=1}^{2n}\left\lfloor\frac{2n}k\right\rfloor\sum_{d|k}\mu(d)B_{k/d}\\ &=\sum_{k=1}^p\left\lfloor\frac pk\right\rfloor\sum_{d|2Qk}\mu(d)B_{2Qk/d}\\ &=\sum_{k=1}^p\left\lfloor\frac pk\right\rfloor\sum_{d|k}\mu\left(\frac kd\right)2^{Q(d,p)}\\ &=\sum_{g|p}2^{Qg}\sum_{k=1}^{\frac pg}\left\lfloor\frac p{kg}\right\rfloor\sum_{d|k}\mu\left(\frac kd\right)\sum_{t|d,t|\frac pg}\mu(t)\\ &=\sum_{g|p}2^{Qg}\sum_{t|\frac pg}\mu(t)\sum_{d=1}^{\frac p{gt}}\sum_{k=1}^{\left\lfloor\frac p{gtd}\right\rfloor}\left\lfloor\frac p{kgtd}\right\rfloor\mu(k)\\ &=\sum_{g|p}2^{Qg}\sum_{t|\frac pg}\mu(t)\sum_{d=1}^{\frac p{gt}}1\\ &=\sum_{g|p}2^{Qg}\sum_{t|\frac pg}\mu(t)\frac p{gt}\\ &=\sum_{g|p}2^{Qg}\phi\left(\frac pg\right)\\ &=\sum_{g|p}2^{n/g}\phi(g)\\ &=\sum_{g|n,g\text{ is odd}}2^{n/g}\phi(g) \end{aligned} $$

嗯，于是我们拿到了 45 分。

Subtask 3

我们考虑求 $g(n)$ 的前缀和 $G(n)$，再随便操作下就能求到 $f(n)$ 的前缀和 $F(n)$ 了。

$$\begin{aligned} G(N)&=\sum_{n=1}^N\sum_{g|n,g\text{ is odd}}2^{n/g}\phi(g)\\ &=\sum_{d=1}2^d\sum_{g=1}^{\left\lfloor\frac Nd\right\rfloor}\left[g\text{ is odd}\right]\phi(g) \end{aligned} $$

我们记

$$S(n)=\sum_{k=1}^n\left[k\text{ is odd}\right]\phi(k) $$

那么 $G(N)=\sum_{d=1}2^dS\left(\left\lfloor\frac Nd\right\rfloor\right)$。预处理好 $10^6$ 之内的 $S(n)$，我们就可以愉快地计算啦～

Subtask 4

我们来观察这个 $S(n)$。首先我们注意到

$$\phi(2n)= \begin{cases} \phi(n),&n\text{ is odd}\\ 2\phi(n),&\text{otherwise.} \end{cases} $$

那么我们设 $H(n)=\sum_{k=1}^n\phi(k)$，则有

$$\begin{aligned} S(n)&=\sum_{k=1}^n\left[k\text{ is odd}\right]\phi(k)\\ &=H(n)-\sum_{k=1}^n\left[k\text{ is even}\right]\phi(k)\\ &=H(n)-\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left[k\text{ is even}\right]\phi(2k)-\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left[k\text{ is odd}\right]\phi(2k)\\ &=H(n)-2\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left[k\text{ is even}\right]\phi(k)-\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left[k\text{ is odd}\right]\phi(k)\\ &=H(n)-2\left(H\left(\left\lfloor\frac n2\right\rfloor\right)-S\left(\left\lfloor\frac n2\right\rfloor\right)\right)-S\left(\left\lfloor\frac n2\right\rfloor\right)\\ &=H(n)-2H\left(\left\lfloor\frac n2\right\rfloor\right)+S\left(\left\lfloor\frac n2\right\rfloor\right)\\ &=H(n)-2H\left(\left\lfloor\frac n2\right\rfloor\right)+H\left(\left\lfloor\frac n2\right\rfloor\right)-2H\left(\left\lfloor\frac n4\right\rfloor\right)+\cdots\\ &=H(n)-H\left(\left\lfloor\frac n2\right\rfloor\right)-H\left(\left\lfloor\frac n4\right\rfloor\right)-H\left(\left\lfloor\frac n8\right\rfloor\right)-\cdots \end{aligned} $$

那么用杜教筛计算 $H(n)$ 即可。这样的话，计算单个 $S(n)$ 会需要计算 $\log n$ 次 $H(n)$，加之我们需要算 $\sqrt N$ 个不同位置的 $S(n)$，看似时间复杂度爆表，实则不然。

记 $D(n)=\left\{n,\left\lfloor\frac n2\right\rfloor,\left\lfloor\frac n3\right\rfloor,\left\lfloor\frac n4\right\rfloor,\cdots\right\}$（不要给我以初中老师的口吻说集合不可重… 自动去重，啊，自动去重），那么我们知道杜教筛在计算 $H(n)$ 时实际上是对 $D(n)$ 中的所有数都计算了一遍 $H(n)$ 并存入了缓存。我们注意到，由于我们求的 $G(N)=\sum_{d=1}2^dS\left(\left\lfloor\frac Nd\right\rfloor\right)$，也就是说我们要求的 $S(x)$ 是满足 $x\in D(N)$ 的，而根据：

定理四：$\left\lfloor\frac{\left\lfloor\frac np\right\rfloor}q\right\rfloor=\left\lfloor\frac n{pq}\right\rfloor$

我们知道我们在求 $S(x)$ 时，需要求的 $H(x),H\left(\left\lfloor\frac x2\right\rfloor\right),H\left(\left\lfloor\frac x3\right\rfloor\right),\dots$ 这些东西实际上也是在 $D(N)$ 中，也就是被计算并缓存过的。因此总的时间复杂度依旧等同于做一次杜教筛的复杂度（当然是计算 $H(n)$ 的部分，其它地方不一定，但不会影响总复杂度），也就是 $O(N^{2/3})$（如果预处理前 $N^{2/3}$ 个 $H(n)$ 的话）。

ametus.h / dream.cpp