P8151 彼岸 | To See the Next Part of the Dream 解题报告

P8151 彼岸 | To See the Next Part of the Dream 解题报告：

更好的阅读体验

下文称奇数集合为 \(\mathbb{O}\)。

题意

对于一个长度为 \(2^n\) 的排列 \(1,2,\cdots,2^n\)，令置换 \(P\) 为 \(x\mapsto 2x\pmod{2^n+1}\)，令 \(f(n)\) 为 \(P^0,P^1,\cdots,P^{n-1}\) 的不动点数量之和，求 \(f\) 的前缀和。

\(1\leqslant n\leqslant 10^{10}\)

分析

思路曲折复杂，需要一定的熟练度与技巧的题。

将置换拆成若干个环，可以发现点 \(x\) 在长度为 \(l\) 约数的环内当且仅当 \((2^l-1)x\equiv0\pmod{2^n+1}\)，也就是：

\[\frac{2^n+1}{\gcd(2^n+1,2^l-1)}\mid x \]

然后联想到经典结论 \(\gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1\)，于是考虑向其转化：

\[\gcd(2^n+1,2^l-1)=\gcd(\frac{2^{2n}-1}{2^n-1},2^l-1)=\frac{2^{\gcd(2n,l)}-1}{2^{\gcd(n,l)}-1} \]

令 \(t_l\) 为长度为 \(l\) 的约数的环数量（显然 \(l\) 是 \(2n\) 的因数，因为 \(2^{2n}l=(2^n+1)(2^n-1)l+l\equiv l\pmod{2^n+1}\)），那么：

若 \(\gcd(2n,l)=\gcd(n,l)\)，那么 \(2^n+1\mid x\)，此时 \(t_l=0\)。

否则，\(\gcd(2n,l)=2\gcd(n,l)\)，那么 \(\dfrac{2^n+1}{2^{\gcd(n,l)}-1}\mid x\)，那么 \(t_l=2^{\gcd(n,l)}\)。

也就是说 \(t_l=\begin{cases}0&\gcd(2n,l)=\gcd(n,l)\\2^{\gcd(n,l)}&\text{otherwise}\end{cases}\)

令 \(p\) 为 \(n\) 分解质因数有多少个 \(2\)，那么 \(t_l\) 非零当且仅当 \(2^{p+1}\mid l\)。

由于环长是 \(2n\) 的约数而不是 \(n\) 的约数，走 \(n\) 步之后每个环都一定走了一半（原因是造成贡献的环长的二幂次至少是 \(2^{p+1}\)，走 \(2n\) 步走完的完整环数量为奇数），那么我们就可以令 \(g(n)\) 为 \(P^0,P^1,\cdots,P^{2n-1}\) 的不动点数量，那么有 \(f(n)=\sum\frac{g(n)+2^n}{2}\)。

我们将上面的”为 \(l\) 约数“莫反，并设 \(n=2^ab\)：

下面要用到的一个式子：\(\sum_{k=1}^n\mu(k)\lfloor\frac{n}{k}\rfloor=\sum_{d=1}^n\sum_{k\mid d}\mu(k)=1\)。

\[g(n)=\sum_{k=1}^{b}\lfloor\frac{2n}{k}\rfloor\sum_{d\mid k\times 2^{a+1}}2^{\gcd(d,b)2^a}\mu(\frac{k}{d})\\=\sum_{p\mid b}2^{2^ap}\sum_{k=1}^{\frac{b}{p}}\lfloor\frac{b}{pk}\rfloor\sum_{d\mid k}\mu(\frac{k}{d})\sum_{z\mid d,z\mid\frac{b}{p}}\mu(z)\\=\sum_{p\mid b}2^{2^ap}\sum_{z\mid\frac{b}{p}}\mu(z)\sum_{d=1}^{\frac{b}{pz}}\sum_{k=1}^{\lfloor\frac{b}{pzd}\rfloor}\mu(k)\lfloor\frac{b}{pzdk}\rfloor\\=\sum_{p\mid b}2^{2^ap}\sum_{z\mid\frac{b}{p}}\mu(z)\sum_{d=1}^{\frac{b}{pz}}1=\sum_{p\mid b}2^{2^ap}\sum_{z\mid\frac{b}{p}}\mu(z)\frac{b}{pz}\\=\sum_{p\mid b}2^{2^ap}\varphi(\frac{b}{p})=\sum_{p\mid n,p\in\mathbb{O}}2^{\frac{n}{p}}\varphi(p) \]

继续推：

\[\sum_{i=1}^ng(i)=\sum_{i=1}^n\sum_{p\mid n,p\in\mathbb{O}}2^{\frac{n}{p}}\varphi(p)\\=\sum_{d=1}^n2^d\sum_{1\leqslant p\leqslant \lfloor\frac{n}{d}\rfloor,p\in\mathbb{O}}\varphi(p) \]

记 \(h(n)=\sum_{i=1}^n[i\in\mathbb{O}]\varphi(i),p(n)=\sum_{i=1}^n\varphi(i)\)，那么有：

\[g(i)=\sum_{d=1}^n 2^dh(\lfloor\frac{n}{d}\rfloor)\\h(n)=p(n)-\sum_{i=1}^n[i\notin\mathbb{O}]\varphi(i)=p(n)-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}[i\in\mathbb{O}]\varphi(2i)-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}[i\notin\mathbb{O}]\varphi(2i)\\=p(n)-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}[i\in\mathbb{O}]\varphi(i)-2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}[i\notin\mathbb{O}]\varphi(i)\\=p(n)-h(\lfloor\frac{n}{2}\rfloor)-2(p(\lfloor\frac{n}{2}\rfloor)-h(\lfloor\frac{n}{2}\rfloor))=p(n)-2p(\lfloor\frac{n}{2}\rfloor)+h(\lfloor\frac{n}{2}\rfloor) \]

归纳可以证明 \(h(n)=p(n)-\sum_{i=1}^{\lfloor\log_2 n\rfloor}p(\lfloor\frac{n}{2^i}\rfloor)\)。

由于杜教筛是块筛（即其可以筛出 \(x=\lfloor\frac{n}{1}\rfloor,\lfloor\frac{n}{2}\rfloor,\cdots,\lfloor\frac{n}{n}\rfloor\) 时函数前缀和的值），所以我们进行一次杜教筛，然后暴力算就好了。

复杂度 \(O(n^{\frac{2}{3}}+\sqrt n\log n)\)。

代码

写的时候偷懒用了 map，实现的也不太精细，不过还是勉强过了。

#include
#include