123E
[ARC123E] Training
多测,求值 \[\sum_{i=1}^{n}\Big[a+\lfloor\frac{i}{b}\rfloor=c+\lfloor\frac{i}{d}\rfloor\Big] \]\(1\le T\le 2\times 10^5\),\(1\le n\le 10^9\),\(1\le a,b,c,d ......
「解题报告」ARC123E Training
挺有趣的题,为数不多的自己能切的题。 题意无非就是要你求 $i \in [1, n]$,有多少满足 $a + \lfloor\frac{i}{b} \rfloor = c + \lfloor\frac{i}{d}\rfloor$。 首先移项,得 $a - c = \lfloor\frac{i}{d} ......
CF123E 题解
简述题意:给你一棵树,每个点有一个被选为起点的概率和一个被选为终点的概率,从起点开始随机遍历子树,问到达终点的期望步数。 直接计算答案很难,考虑对一对 $(S,T)$ 来说,以 $S$ 为根,那么有: 对 $T$ 的子树里的点:显然不会被遍历到,贡献为 $0$。 对 $S\to T$ 路径上的点:显 ......