Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

「2021.4.2 纪中集训」总结

posted on 2021-04-02 22:17:45 | under 总结 |

无聊的话写在前面

  • T2看错题浪费了一个多小时......

  • T3就是道EGF的简单题,居然没想出来(昨晚还熬夜看了下生成函数)

  • 错过提交

  • CCF一些脑袋灵光的人把初赛时间定到了今年的9.18

  • 往事都随风,只剩下一股执念留在心里挥之不去

2006.3.20-2021.4.2

总结

T2

  • $\displaystyle f(n)=\sum_{i=1}^n\sum_{j=1}^n\mu(ij)$

  • $\displaystyle g(n)=\sum_{i=1}^n\sum_{j=1}^nij[i\perp j]$

  • $\displaystyle F(S)=\sum_{T\subseteq S}f(\gcd(T))\prod_{a\in T}g(a)$

给定序列$\{a_n\}$,对每个$i=1,\cdots,n$,求$F(\{a_{1,..,i}\})$,强制在线.

题解

不急,一个一个来

Part 1

若$i,j$有相同的质因数,则$ij$含平方质因子,即$\mu(ij)=0$,否则有$i\perp j$,即$\mu(ij)=\mu(i)\mu(j)$.

拆开式子后套莫比乌斯反演$$\begin{aligned}f(n)&=\sum_{i=1}^n\sum_{j=1}^n\mu(i)\mu(j)[i\perp j]\\&=\sum_{i=1}^n\sum_{j=1}^n\mu(i)\mu(j)\sum_{k|i,k|j}\mu(k)\\&=\sum_{k=1}^n\mu(k)\left(\sum_{k|i,i\le n}\mu(i)\right)^2\\&=\sum_{i=1}^n\mu(i)S^2_{i,n}\end{aligned}$$ 其中$\displaystyle S_{d,n}=\sum_{d|i,i\le n}\mu(i)$,对$f(n)$差分得$$\begin{aligned}\Delta f(n)&=\sum_{d|n}\mu(d)S^2_{d,n}-\sum_{d|n}\mu(d)S^2_{d,n-1}\\&=\sum_{d|n}\mu(d)(2S_{d,n-1}+\mu(n))\mu(n)\end{aligned}$$ 考虑枚举$d$,再枚举$d$的倍数$kd$,将$\mu(d)(2S_{(k-1)d,d}+\mu(kd))\mu(kd)$贡献到$\Delta f(kd)$,做一遍前缀和即可预处理出所有的$f$,时间复杂度为$\mathcal O(n\log n)$.

Part 2

设$n>1$,则$\gcd(i,n)=1$蕴含着$\gcd(n-i,1)=1$,这意味着n以内互质的数是成对存在的,且每对的和恰好为n,即$$\sum_{i=1}^n i[i\perp n]=\frac{1}{2}\varphi(n)$$ 于是$$g(n)=\sum_{i=1}^n\sum_{j=1}^nij[i\perp j]=\sum_{i=1}^ni^2\varphi(i)$$ 线性递推出所有$g(n)$即可.

Part 3

现在我们已经预处理出了所有的$f(n)$和$g(n)$的值,考虑求$F(s)$.

$\gcd(T)$的性质促使我们考虑这样一个函数$h$,满足$$f(n)=\sum_{d|n}h(d)\iff h(n)=\sum_{d|n}f(d)\mu\left(\frac{n}{d}\right)$$ 代入得$$\begin{aligned}F(S)&=\sum_{T\subseteq S}\sum_{d|\gcd(T)}h(d)\prod_{a\in T}g(a)\\&=\sum_{d=1}^mh(d){\color{green} \left[\prod_{d|a,a\in S}(g(a_i)+1)-1\right]}\end{aligned}$$$h$可以$\mathcal O(n\log\log n)$或$\mathcal O(n\log n)$预处理,接下来考虑绿色部分,记它为$G(d)$.

每插入一个$a_i$时,暴力枚举它的因数并修改$F$和$G$的值即可,考虑到$a_i$两两不同,复杂度仍为$\mathcal O(n\log n)$.

这真是道有趣的数论题!

T3

题意大意:统计满足以下条件的$r×n$矩阵的个数

  • 每一行的数为$1$到$n$的排列.

  • 若$k|i$,则第$i$列的每一行的元素都大于第$i+1$列每一行对应的元素,否则,第$i$列每一行元素都小于第$i+1$列每一行对应的元素

其中$k$是一个给定的整数.

题解

设$r=1$,考虑容斥,有$i$个$k$的倍数处非法的矩阵个数$C$对答案有$(-1)^iC$的贡献,基于此,定义两个幂级数$$F(x)=\sum_{i=1}^{\infty}(-1)^{i-1}\frac{x^{ki}}{(ki)!}$$$$G(x)=\sum_{i=0}^{\infty}(-1)^{i}\frac{x^{ki+r}}{(ki+r)!}$$ 其中$n\equiv r\pmod{k}$,且$r<k$.

$F$的每一项的含义为一段极长的,上升的,且长度为$k$的倍数的子段,系数代表它的非法点个数,$G$的含义是将没填的部分补齐.

考虑选取$0,1,2,\cdots$个这样的子段,不难得出最终的答案为$$[\frac{x^n}{n!}]G(x)(1+F(x)+F^2(x)+\cdots)=[\frac{x^n}{n!}]\frac{G(x)}{1-F(x)}$$ 多项式求逆即可.

没意思~