差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:farmer_john:week_15 [2020/08/14 11:07]
2sozx [2sozx]
+++ 2020-2021:teams:farmer_john:week_15 [2020/10/26 06:58] (当前版本)
203.208.60.12 ↷ 链接因页面移动而自动修正
@@ 行 3: / 行 3: @@
 |2020-08-08| [[2020牛客暑期多校第九场]] |  6  |  10  |  12  |52/975|
 |2020-08-10| [[2020牛客暑期多校第十场]] |  5  |  6  |  10  |23/906|
-|2020-08-13| [[2020 Multi-University Training Contest 6|HDU 2020 Multi-University Training Contest 6]] |  7  |  8  |  11  |73/792|
+|2020-08-13| [[2020hdu暑期多校第六场|HDU 2020 Multi-University Training Contest 6]] |  7  |  8  |  11  |73/792|
 ===== 本周推荐 =====
 ====2sozx====
@@ 行 17: / 行 17: @@
   * comment：炉石传说真尼玛好玩
 ====Bazoka13====
-===题目名称===
+===2020HDU多校第六场D Asteroid in Love ===
-  * 分类：
+  * 分类：计算几何
-  * 题意：
+  * 题意：给定平面里的$n$个点，每个点有一个种类，共计三个种类，每个种类选出一个点，选出三个点，使得三个点组成的三角形面积最大
   * 题解：
+           - 数字列表项目显然可以通过枚举某两个种类的点，然后去找距离当前构成的线段距离最远的点，而距离最远的点一定是在第三类点所构成的凸包上，那么只需要求出第三种点的上下凸包，然后跑一个三分即可。
+           - 由于不知道是凸凹函数，需要都跑一遍，但是有可能会出现双峰的情况，换一个方向再跑一遍即可。
-  * comment：
+  * comment：日常撞大运出正解（不过$std$貌似只跑了一遍？）
 ====JJLeo===
-===题目名称===
+===2020HDU多校第六场G A Very Easy Math Problem===
-  * 分类：
+  * 分类：数论，莫比乌斯反演。
-  * 题意：
+  * 题意：给定$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：
+  * comment：非常适合数论萌新入门的反演题。
 =====个人训练=====
 ===== 2sozx =====
 ==== 比赛 ====
+  * 2020.08.12 [[.2sozx:Codeforces Round 664 (Div. 2)|Codeforces Round #664(Div. 2)]]
 ==== 题目 ====
 ===== Bazoka13 =====
@@ 行 47: / 行 51: @@
 ==== 题目 ====
+  * [[莫比乌斯反演技巧总结]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具