比赛链接

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$$ 因此求出前缀和，对于每个除以一下区间长度，最后再除以总方案数即可。

solved by 2sozx

给出一个式子 $a \ opt \ b \ = \ c$ ，中间无空格，问在二至十六进制下哪个进制可以使得等式成立。 $opt=+,-,*,/$

模拟即可，注意进制没有一进制，即 $0+0=0$ 最少也是在二进制下成立。

upsolved by

$(10,1,1) (6,4,2) (6,5,1)$ 我裂开

solved by Bazoka13

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

1. 显然可以通过枚举某两个种类的点，然后去找距离当前构成的线段距离最远的点，而距离最远的点一定是在第三类点所构成的凸包上，那么只需要求出第三种点的上下凸包，然后跑一个三分即可。
2. 由于不知道是凸凹函数，需要都跑一遍，但是有可能会出现双峰的情况，换一个方向再跑一遍即可。

solved by JJLeo

将$1145141919$循环无限次得到一个字符串，现在需要选取一个前缀，将这个前缀添加任意数量的$()\times+$使得表达式的值等于$x$，问对于$x=1,2, \cdots , 5000$，选取的最短前缀长度是多少，或判断无解。

选取前$11$个数打个表发现除了$3,7$都有解，然后就完事了。

solved by Bazoka13 JJLeo

第$i$条路径的权值是$2^i$，每个点要么是黑色，要么是白色，求所有异色点最短路的长度总和

根据等比数列，显然有前$i-1$项总和小于第$i$项，那么求一个最小生成树然后$dfs$处理两侧异色点数即可

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})$。

upsolved by JJLeo

solved by JJLeo

给定$b$和$x$，问是否满足一个数是$x$的倍数等价于该数在$b$进制下的各数位上数字之和是$x$的倍数。

最常见的满足条件的有十进制下的$3$和$9$，盲猜满足条件等价于$x \equiv 1 \pmod{b}$就过了。

solved by 2sozx JJLeo

给定一个$n$个点的无向图，每条边有边权，定义生成树的权值为所有树边边权的$\operatorname{AND}$，求生成树权值的期望，对$998244353$取模。$(n \le 100)$

按位考虑进行计算，枚举最终答案有每一位有多少种方案，通过只选择该位位$1$的边然后套用矩阵树定理即可。最后把所有边都算上再使用一个矩阵树定理计算出生成树总数，除以该数量即可。

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多校，同时不要每次都死在概率与期望上。