======2020HDU暑期多校第六场====== [[https://vjudge.net/contest/389024|比赛链接]] =====A.===== **solved by JJLeo** ====题意==== 给出一个序列，等概率地选择左右端点$l \le r$，求$[l,r]$区间平均数的期望值。 ====题解==== 题目本质是问长度为$1,2, \cdots , n$的连续子区间中，每个数各出现了多少次。可以发现如下规律：$$1 1 1 1 1 1 1$$ $$1 2 2 2 2 2 1$$ $$1 2 3 3 3 2 1$$ $$1 2 3 4 3 2 1$$ $$1 2 3 3 3 2 1$$ $$1 2 2 2 2 2 1$$ $$1 1 1 1 1 1 1$$ 因此求出前缀和，对于每个除以一下区间长度，最后再除以总方案数即可。 =====B.===== **solved by 2sozx** ====题意==== 给出一个式子 $a \ opt \ b \ = \ c$ ，中间无空格，问在二至十六进制下哪个进制可以使得等式成立。 $opt=+,-,*,/$ ====题解==== 模拟即可，注意进制没有一进制，即 $0+0=0$ 最少也是在二进制下成立。 =====C.===== **upsolved by ** ====题意==== $(10,1,1) (6,4,2) (6,5,1)$ 我裂开 ====题解==== =====D.===== **solved by Bazoka13** ====题意==== 给定平面里的$n$个点，每个点有一个种类，共计三个种类，每个种类选出一个点，选出三个点，使得三个点组成的三角形面积最大 ====题解==== - 显然可以通过枚举某两个种类的点，然后去找距离当前构成的线段距离最远的点，而距离最远的点一定是在第三类点所构成的凸包上，那么只需要求出第三种点的上下凸包，然后跑一个三分即可。 - 由于不知道是凸凹函数，需要都跑一遍，但是有可能会出现双峰的情况，换一个方向再跑一遍即可。 =====E.===== **solved by JJLeo** ====题意==== 将$1145141919$循环无限次得到一个字符串，现在需要选取一个前缀，将这个前缀添加任意数量的$()\times+$使得表达式的值等于$x$，问对于$x=1,2, \cdots , 5000$，选取的最短前缀长度是多少，或判断无解。 ====题解==== 选取前$11$个数打个表发现除了$3,7$都有解，然后就完事了。 =====F.===== **solved by Bazoka13 JJLeo** ====题意==== 第$i$条路径的权值是$2^i$，每个点要么是黑色，要么是白色，求所有异色点最短路的长度总和 ====题解==== 根据等比数列，显然有前$i-1$项总和小于第$i$项，那么求一个最小生成树然后$dfs$处理两侧异色点数即可 =====G.===== **upsolved by 2sozx Bazoka13 JJLeo** ====题意==== 给定$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})$。 =====H.===== **upsolved by JJLeo** ====题意==== ====题解==== =====I.===== **solved by JJLeo** ====题意==== 给定$b$和$x$，问是否满足**__一个数是$x$的倍数__**等价于**__该数在$b$进制下的各数位上数字之和是$x$的倍数__**。 ====题解==== 最常见的满足条件的有十进制下的$3$和$9$，盲猜满足条件等价于$x \equiv 1 \pmod{b}$就过了。 =====J.===== **solved by 2sozx JJLeo** ====题意==== 给定一个$n$个点的无向图，每条边有边权，定义生成树的权值为所有树边边权的$\operatorname{AND}$，求生成树权值的期望，对$998244353$取模。$(n \le 100)$ ====题解==== 按位考虑进行计算，枚举最终答案有每一位有多少种方案，通过只选择该位位$1$的边然后套用矩阵树定理即可。最后把所有边都算上再使用一个矩阵树定理计算出生成树总数，除以该数量即可。 =====K.===== **upsolved by ** ====题意==== ====题解==== =====记录===== 0min：开局分题\\ 8min：ZYF猜结论 AC I ，MJX冲B\\ 18min：MJX WA B\\ 28min：MJX AC B，CSK 冲F\\ 60min：CSK WA3，换ZYF冲A\\ 61min：ZYF AC A，冲J\\ 66min：ZYF AC J，冲E\\ 68min：CSK AC F\\ 101min：ZYF AC E\\ 101min~210min：自闭ing\\ 210min：CSK冲D，ZYF MJX 冲C\\ 269min：CSK AC D\\ till end：C应该是想错了\\ after end：G式子推出来了结果 $n$ 范围看错了 =====总结===== * MJX：要认真看数据范围，不要把 $10^5$ 当作 $10^9$ * CSK：别读错题，别读错题，别读错题，% ZYF * ZYF：要学习更多的知识点以应对毒瘤的HDU多校，同时不要每次都死在概率与期望上。