526互联

CF1205题解

发布时间 2023-12-13 22:12:29作者: cool_tyl

CF1205 Expected Value Again

首先算 \(\sum f^2(s)\)，一个很经典的转化：任选 \(i,j < n\) 满足 \(i,j\) 同时是 border。
摆出几个结论：

  • \(r\) 是 \(s\) 的 border 等价于 \(|s| - r\) 是 \(s\) 的周期。
  • 弱周期定理：若 \(p,q\) 同时是 \(s\) 的周期，且 \(p+q \leq |s|\)，则 \(\gcd(p,q)\) 也是 \(s\) 的周期。

令 \(i'=n-i,j'=n-j\)，则当 \(i'+j' \leq n\) 时，等价于 \(\gcd(i',j')\) 为周期，因此方案数为 \(k^{\gcd(i,j)}\)。
而当 \(i'+j'>n\) 时，情况略有不同。
先满足 \(i'\) 的限制，相当于将原始下标按 \(\bmod i'\) 划分为 \(i'\) 个联通块，然后加上 \(j'\)，也就是对于 \(\leq n-j\) 的点 \(i\) 连向 \(i+j\)，经过手玩可知，对于前 \(i-\gcd(i,j)\) 个点连出去的边是不会成环的，而后 \(\gcd(i,j)\) 个点的边是会成环的，因此最后联通块的数量为 \(i'-(n-j')+\max(0, n-j'-(i'-\gcd(i',j')))=\max(i'+j'-n,\gcd(i',j'))\)。

以上两种情况可以写成统一形式：\(k^{\max(\gcd(i',j'),i'+j'-n)}\)。
所以最后答案 \(ans \times k^n=k^{\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}\max(i+j-n,\gcd(i,j))}\)。

下面就是喜闻乐见的推式子环节：
先假设 \(\max\) 全部取 \(i+j-n\)，拆掉 \(\max\)（\(\max(a,b)=b+(a-b)[a>b]\)）：

\[\begin{aligned} &\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}k^{i+j-n} \\ &=k^{-n}\sum_{s=2}k^s\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[i+j=s]\\ &=k^{-n}\sum_{s=2}k^s\min(k-1,2n-1-k) \end{aligned} \]

第二部分：

\[\begin{aligned} &\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}(k^{\gcd(i,j)}-k^{i+j-n})[\gcd(i,j)>i+j-n] \\ &=\sum_{d=1}^{n-1}\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}(k^d-k^{i+j-n})[d>i+j-n] \\ &=\sum_{d=1}^{n-1}\sum_{i=1}^{\lfloor \frac{n-1}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n-1}{d}\rfloor}(k^d-k^{id+jd-n})[d>id+jd-n][\gcd(i,j)=1] \\ \end{aligned} \]

这之后有两种推法：

Solution 1

直接上莫比乌斯反演：

\[\begin{aligned} &\sum_{d=1}^{n-1}\sum_{i=1}^{\lfloor \frac{n-1}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n-1}{d}\rfloor}(k^d-k^{id+jd-n})[d>id+jd-n][\gcd(i,j)=1] \\ &=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor \frac{n-1}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n-1}{d}\rfloor}\sum_{c|i,c|j}\mu(c)(k^d-k^{id+jd-n})[d>id+jd-n] \\ &=\sum_{d=1}^{n}\sum_{c|d}\mu(c)\sum_{i=1}^{\lfloor \frac{n-1}{cd}\rfloor}\sum_{j=1}^{\lfloor \frac{n-1}{cd}\rfloor}(k^d-k^{icd+jcd-n})[d>icd+jcd-n]\\ &=\sum_{T=1}^{n-1}\sum_{d|T}\mu(\frac{T}{d})\sum_{i=1}^{\lfloor \frac{n-1}{T}\rfloor}\sum_{j=1}^{\lfloor \frac{n-1}{T}\rfloor}(k^d-k^{iT+jT-n})[d>iT+jT-n] \end{aligned} \]

拆成两部分：

  • Part 1

    \[\begin{aligned} &\sum_{T=1}^{n-1}\sum_{d|T}\mu(\frac{T}{d})\sum_{i=1}^{\lfloor \frac{n-1}{T}\rfloor}\sum_{j=1}^{\lfloor \frac{n-1}{T}\rfloor}k^d[d>iT+jT-n] \end{aligned} \]

    令 \(S(k,d)=\sum_{i=1}^{k}\sum_{j=1}^{k}k^d[d>ik+jk-n]\)。

    易知 \([d>ik+jk-n]=[i+j\leq\lfloor\frac{n+d-1}{k}\rfloor]\)，所以 \(S\) 的计算相当于把正方形截去一个角，很容易 \(\mathcal{O}(1)\) 计算。

    因此原式 \(=\sum_{T=1}^{n-1}\sum_{d|T}\mu(\frac{T}{d})k^dS(T,d)\)，枚举 \(T\) 和 \(d\) 即可做到 \(\mathcal{O}(n\log n)\)。

  • Part 2

    \[\begin{aligned} &\sum_{T=1}^{n-1}\sum_{d|T}\mu(\frac{T}{d})\sum_{i=1}^{\lfloor \frac{n-1}{T}\rfloor}\sum_{j=1}^{\lfloor \frac{n-1}{T}\rfloor}k^{iT+jT-n}[i+j\leq\lfloor\frac{n+d-1}{T}\rfloor]\\ &=k^{-n}\sum_{T=1}^{n-1}\sum_{d|T}\mu(\frac{T}{d})\sum_{i=1}^{\lfloor \frac{n-1}{T}\rfloor}\sum_{j=1}^{\lfloor \frac{n-1}{T}\rfloor}k^{T(i+j)}[i+j\leq\lfloor\frac{n+d-1}{T}\rfloor] \end{aligned} \]

    直接枚举 \(T,d,i\)，那么合法的 \(j\) 是一个前缀，预处理 \(k^T\) 的幂和即可做到 \(\mathcal{O}(n\log^2n)\)。
    但有一个更聪明的办法：把后面的式子看成关于 \(k^T\) 的多项式，那么一个合法的 \(i,j\) 就会给第 \(i+j\) 项系数做贡献，注意到 \(d\leq T\)，因此 \(\lfloor\frac{n+d-1}{T}\rfloor\leq\lfloor\frac{n+T-1}{T}\rfloor=\lfloor\frac{n-1}{T}\rfloor+1\)，因此对于一个 \(x=i+j\)，它被枚举到的次数为 \(x-1\)，用二阶差分维护系数即可做到 \(\mathcal{O}(n\log n)\)。

Solution 2

原来的式子：

\[\sum_{d=1}^{n-1}\sum_{i=1}^{\lfloor \frac{n-1}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n-1}{d}\rfloor}(k^d-k^{id+jd-n})[i+j\leq \lfloor\frac{n-1}{d}\rfloor+1][\gcd(i,j)=1] \]

这里不考虑反演，考虑直接枚举 \(s=i+j\)：

\[\begin{aligned} &\sum_{d=1}^{n-1}\sum_{s=2}^{\lfloor\frac{n-1}{d}\rfloor+1}\sum_{i=1}^{s-1}(k^d-k^{sd-n})[\gcd(i,s-i)=1]\\ &=\sum_{d=1}^{n-1}\sum_{s=2}^{\lfloor\frac{n-1}{d}\rfloor+1}(k^d-k^{sd-n})\sum_{i=1}^{s-1}[\gcd(i,s)=1]\\ &=\sum_{d=1}^{n-1}\sum_{s=2}^{\lfloor\frac{n-1}{d}\rfloor+1}(k^d-k^{sd-n})\varphi(s) \end{aligned} \]

还是拆分成两个部分：

  • Part 1

    \[ \sum_{d=1}^{n-1}\sum_{s=2}^{\lfloor\frac{n-1}{d}\rfloor+1}k^d\varphi(s) =\sum_{d=1}^{n-1}k^d\sum_{s=2}^{\lfloor\frac{n-1}{d}\rfloor+1}\varphi(s) \]

    所以只用求 \(\varphi\) 的前缀和即可。

  • Part 2

    \[ \sum_{d=1}^{n-1}\sum_{s=2}^{\lfloor\frac{n-1}{d}\rfloor+1}k^{sd-n}\varphi(s) \]

    看似不是很好处理，但有一个很高妙处理：
    还记得我们在前面钦定所有 \(\max\) 均取了 \(i+j-n\) 吗，我们知道当 \(i+j-n \leq 0\) 时 \(\max\) 一定取到 \(\gcd\)，因此我们在前面只加上 \(i+j-n>0\) 的部分，这里也只用处理 \(i+j-n>0\) 的部分，也即 \(sd>n\)，发现当 \(d\) 不能整除 \(n\) 时，\(sd>n\) 完全等价于 \(s\geq \lfloor\frac{n-1}{d}\rfloor+1\)，因此只有一项是合法的！而当 \(d|n\) 时，\((\lfloor\frac{n-1}{d}\rfloor+1)d=n\)，也就是说没有任何一项满足！
    至此我们就可以 \(\mathcal{O}(n)\) 解决这道题。