| 排名 |
当场过题数 |
至今过题数 |
总题数 |
| 73/792 |
7 |
9 |
11 |
A
solved by JJLeo
题意
给出一个序列，等概率地选择左右端点\(l \le r\)，求\([l,r]\)区间平均数的期望值。
题解
题目本质是问长度为\(1,2, \cdots , n\)的连续子区间中，每个数各出现了多少次。可以发现如下规律：
\[
\begin{aligned}
1 1 1 1 1 1 1 \newline
1 2 2 2 2 2 1 \newline
1 2 3 3 3 2 1 \newline
1 2 3 4 3 2 1 \newline
1 2 3 3 3 2 1 \newline
1 2 2 2 2 2 1 \newline
1 2 2 2 2 2 1 \newline
1 1 1 1 1 1 1 \newline
\end{aligned}
\]
因此求出前缀和，对于每个除以一下区间长度，最后再除以总方案数即可。
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多校，同时不要每次都死在概率与期望上。