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$ 的...
B 被降智了，所以掉分了。A考虑将这个串拆成三部分考虑：114，5，14。设 $f_{i,j}$ 表示 114 的 $4$ 的位置是 $i$，1 代表 $j$ 的方案数，$g_{i,j}$ 表示 14 中 1 的位置是 $i$，4 代表 $j$ 的方案数，另外记录一个 $s_{i,j}$ 表示前 $i$ 个字符中 $j$ 的数量，字符串是 $a$，那么答案是：我们枚举 $i$ 和 $a_j$...
A打表可以发现 $k>1$ 先手必胜，$k=1$ 取决于 $n$ 的奇偶性。具体证明：考虑如果 $n$ 是奇数的话，先手第一步取中间的那一块，序列变成了互相独立的两部分，之后先手只需要在没有被后手操作的块里模拟后手动作即可。如果 $n$ 是偶数的话，$k>1$ 也可以类似的划分成两段长度相等的段。$k=1$ 等价于每次只能取一个，所以 $n$ 是偶数的话后手能赢。#include...
A. 异或考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。#include <bits/stdc++.h> #define fi first #define se second #define db...
A. 星际穿越感觉也很神。。先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。考虑 $r$ 往左走的最短路径是怎么走的：引理一：往右走之前一定不会往左走反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。引理二：不会存在连续的两次往右走反证法。如果存在两次连续的...