AGC038 部分题解
E题意有一个随机数生成器，生成 $[0,n-1]$ 之内的数，生成第 $i$ 个数的概率为 $\frac{A_i}{S}$，其中 $S=\sum_{i=1}^n A_i$。当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成，求期望生成次数，对大质数取模。题解设第 $i$ 个数最后一次被随机到的时间为 $t_i$，答案就是 $\max t_i$ 的...
E题意有一个随机数生成器，生成 $[0,n-1]$ 之内的数，生成第 $i$ 个数的概率为 $\frac{A_i}{S}$，其中 $S=\sum_{i=1}^n A_i$。当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成，求期望生成次数，对大质数取模。题解设第 $i$ 个数最后一次被随机到的时间为 $t_i$，答案就是 $\max t_i$ 的...
A如果长度为 $2$ 特判，否则将第一个数和剩下的数分开。B$B$ 进制下正整数的数根等价于 $\pmod {B-1}$，注意这里 $0$ 对应的答案是 $B-1$。所以答案是 $(k-1)B+x$。C双指针扫出所有相同的段，每段取前 $k$ 大即可。D观察一下发现只需要枚举 $x|n$，然后前缀和预处理+判断所有矩阵是不是全 $0/1$ 矩阵即可。时间复杂度分析一波：先考虑行的贡献，枚举的...
A两人策略不会互相造成影响，最优策略是每个人每次拿一个。判断是否 $n_1 \leq n_2$ 即可。B先考虑如何计算一个排列的 $f$：设一个位置左边和右边第一个比他小的位置为 $ls_i,rs_i$，答案就是 $\sum_{i=1}^n a_i(rs_i-ls_i-1)$。另一种思考思路是从小往大放，每次相当于将选出的位置分成左右两个连通块，每次得到的贡献是它所在的连通块跨过它的区间个数...
A$x$ 取在 $\sqrt d$ 附近，枚举一下就行了。B对于任意一个二元组 $(x,y)$，设 $y$ 的位数为 $t$，那么合法的 $x$ 当且仅当满足 $xy+x+y = x\times 10^t + y$。 化简一下可以得到 $y = 10^t - 1$。而发现这个式子对 $x$ 是没限制的，也就是说如果 $y$ 合法那么 $x$ 可以任意选。所以 $y$ 其实只能取形如 $9,9...
A如果满足条件可以注意到一定有 $a_i = a_{i+k} = a_{i+2k} = \ldots$，所以先判断这个，然后只需要判断 $[1 \ldots k]$ 能否被填成平衡的串即可。B如果先手一步能抓住后手，那么先手必胜。如果 $db \leq 2da$，那么一定存在一个时间后手被先手逼到角落里但是后手无法通过向先手的范围跳跃而跳出攻击范围。那么按照后手的意愿，先后手最后的稳定状态一...