CVBB ACM Team

分类：模拟

题意：炉石传说背景，有四种随从：一.剧毒；二.剧毒圣盾；三.剧毒亡语；四.剧毒圣盾亡语。其中亡语生成一个 $1/1$ 的植物，其余随从为 $1/10^9$，现在你拥有一些随从，电脑拥有一些随从，问在你做出最优决策，电脑做出最劣决策下你是否能赢。

comment：炉石传说真尼玛好玩

分类：计算几何

题意：给定平面里的$n$个点，每个点有一个种类，共计三个种类，每个种类选出一个点，选出三个点，使得三个点组成的三角形面积最大

comment：日常撞大运出正解（不过$std$貌似只跑了一遍？）

分类：数论，莫比乌斯反演。

题意：给定$k$与$x$，$t$次询问，每次询问给定一个$n$，求$$\sum_{a_1=1}^{n}\sum_{a_2=1}^n\dotsb\sum_{a_x=1}^n\left(\prod_{j=1}^xa_j^k\right)f\left(\gcd\left(a_1,a_2,\dots,a_x\right)\right)\cdot \gcd\left(a_1,a_2,\dots,a_x\right) \pmod{{10}^9+7}$$其中$f(n)$定义如下：如果存在正整数$k$使得$k^2|n$，那么$f(n)=0$，否则$f(n)=1$。$$(1\le t \le 10^4,1\le k\le 10^9,1\le x\le 10^9,1\leq n\leq 2\times10^5)$$

题解：首先，容易证明以下两个等式成立，以便反演中使用$$f(n)=|\mu(n)|=\mu^2(n)$$$$\sum_{a_1=1}^{n}\sum_{a_2=1}^n\dotsb\sum_{a_x=1}^n\left(\prod_{j=1}^xa_j^k\right)=\left(\sum_{i=1}^ni^k\right)^x$$接下来我们开始反演$$\sum_{a_1=1}^{n}\sum_{a_2=1}^{n}\ldots \sum_{a_x=1}^{n}\left (\prod_{j=1}^{x}a_j^k\right )f(\gcd(a_1,a_2,\ldots ,a_x))\cdot \gcd(a_1,a_2,\ldots ,a_x)$$枚举$d=\gcd(a_1,a_2,\ldots ,a_x)$$$=\sum_{d=1}^n\mu^2\left(d\right)d\sum_{a_1=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{a_2=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\dotsb\sum_{a_x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\left(\prod_{j=1}^x(a_jd)^k\right)[\gcd\left(a_1,a_2,\dots,a_x\right)=1]$$$$=\sum_{d=1}^n\mu^2\left(d\right)d^{kx+1}\sum_{a_1=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{a_2=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\dotsb\sum_{a_x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\left(\prod_{j=1}^xa_j^k\right)[\gcd\left(a_1,a_2,\dots,a_x\right)=1]$$利用$\epsilon = \mu * 1$$$=\sum_{d=1}^n\mu^2\left(d\right)d^{kx+1}\sum_{a_1=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{a_2=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\dotsb\sum_{a_x=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\left(\prod_{j=1}^xa_j^k\right)\sum_{p|\gcd(a_1,a_2,\dots,a_x)}\mu(p)$$枚举$p$$$=\sum_{d=1}^n\mu^2\left(d\right)d^{kx+1}\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\sum_{a_1=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\sum_{a_2=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\dotsb\sum_{a_x=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\left(\prod_{j=1}^x(a_jp)^k\right)$$$$=\sum_{d=1}^n\mu^2\left(d\right)d^{kx+1}\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)p^{kx}\sum_{a_1=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\sum_{a_2=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\dotsb\sum_{a_x=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\left(\prod_{j=1}^xa_j^k\right)$$$$=\sum_{d=1}^n\mu^2\left(d\right)d^{kx+1}\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)p^{kx}\left(\sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}i^k\right)^x$$$$=\sum_{d=1}^n\mu^2\left(d\right)d\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p){(dp)}^{kx}\left(\sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}i^k\right)^x$$令$T=dp$，枚举$T$$$=\sum_{T=1}^n{T}^{kx}\left(\sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}i^k\right)^x\sum_{d|T}\mu^2\left(d\right)\mu(\frac{T}{d})d$$$$=\sum_{T=1}^n\left(\sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}i^k\right)^x{T}^{kx}\sum_{d|T}\mu^2\left(d\right)\mu(\frac{T}{d})d$$设$$F(n)=\left(\sum_{i=1}^{n}i^k\right)^x$$$$G(n)={n}^{kx}\sum_{d|n}\mu^2\left(d\right)\mu(\frac{n}{d})d$$则所求式子化为$$\sum_{T=1}^{n}F(\left\lfloor \frac{n}{T} \right\rfloor)G(T)$$$O(n \log n)$分别处理出$F(n)$和$G(n)$，对于每组询问$O(\sqrt{n})$整除分块即可，总复杂度$O(n \log n + t \sqrt{n})$。

comment：非常适合数论萌新入门的反演题。

2020.08.12 Codeforces Round #664(Div. 2)

莫比乌斯反演技巧总结