Solution

A. The friends

题目大意：在 \([B_{1},B_{2}]\) 中等概率随机一个整数 \(b\)，在 \([J_{1},J_{2}]\) 中等概率随机一个整数 \(j\)，若 \(b^{j}=j^{b}\)，则重新随机，直到它们不相等。求 \(b^{j}>j^{b}\) 和 \(b^{j}<j^{b}\) 的概率。

题解：两边取 \(\ln\) 有 \(j\ln b>b\ln j\)，即 \(\displaystyle{\frac{\ln b}{b}>\frac{\ln j}{j}}\)，求导得 \(\displaystyle(\frac{\ln x}{x})'=\frac{1-\ln x}{x^{2}}\)，即该函数从 \([1,e)\) 递增，\((e,\infty)\) 递减，实际计算后可得 \(f(3)>f(2)=f(4)>f(5)>f(6)>\cdots>f(1)\)。

注意到除了 \(1,2,3,4\) 外，该函数单调递减。我们可以先假定 \(b<j\) 时，\(b^{j}>j^{b}\)，先计算出满足要求的 \(b,j\) 对数，这可以转换为一个矩形和 \(y=x\) 相交后下半部分的面积（这个xjb算一下就好）。之后我们考虑有哪些情况算错了：

• \(b=3,j=2\) 算少了 \(1\)
• \(b=2,j=4\) 算多了 \(1\)
• \(b=1\) 算多了 \(J_{2}-J_{1}+1\)（注意 \(j=1\)）
• \(b=2,j=3\) 算多了 \(1\)
• \(j=1\) 算少了 \(B_{2}-B_{1}+1\)（注意 \(b=1\)）

B. The cities

题目大意：给出平面上的 \(n\) 个点，不断从中等概率随机选取三角形，问这 \(\lfloor\frac{n}{3}\rfloor\) 个三角形的期望总面积。

题解：显然每个三角形被选择的概率为 \(\displaystyle \frac{\lfloor\frac{n}{3}\rfloor}{{n\choose 3}}\)，那么我们只需要将它乘上所有三角形的总面积即可。

我们枚举三角形的两个顶点 \(A(x_{1},y_{1}),B(x_{2},y_{2})\)，对于剩下的一个顶点 \(C(x_{3},y_{3})\)，容易用叉乘计算面积：\(\displaystyle \frac{|(x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})|}{2}\)。若 \(C\) 在射线 \(AB\) 的左侧，那么绝对值中非负，反之非正。我们可以将所有满足要求的 \(B\) 按极角排序，维护两个 pointer，一个指向当前点，一个指向它转 \(180^{\circ}\) 范围内最远的点，将 \(B\) 按极角序旋转一圈即可。

时间复杂度 \(\mathcal{O}(n^{2}\log n)\)。

D. The almost lucky numbers

题目大意：定义 \(4,7\) 为幸运数字，\(3,5,6,8\) 为准幸运数字，定义幸运数为完全由幸运/准幸运数字组成，且幸运数字不少于准幸运数字的数，求 \([A,B]\) 中幸运数的个数。

题解：经典数位 dp，按套路分解以后做就好了。

E. The flights

题目大意：\(n\) 个点 \(m\) 条无向边的图 \(G\)，现在要给 \(G\) 加 \(n\) 条有向边，满足每个点恰好有一条出边和入边，并且图 \(G\) 中同一连通块中的点之间不能连有向边，求方案数 mod 1234567891。

（有多少排列满足 \(i\) 和 \(p_i\) 不在同一个连通块。）

题解：考虑容斥计算，\(\displaystyle ans = \sum\limits_{k=0}^n(-1)^kf(k)\times(n-k)!\).

其中 \(f(k)\) 为恰好有 \(k\) 条不合法边的方案数。

\(\displaystyle f(k) = \prod\limits_{i=0,\sum a_i = k}^{m} \binom{s_i}{a_i}^2\times a_i!\)，其中 \(s_i\) 为第 \(i\) 个连通块大小。

直接并查集求连通块之后背包求 \(f(k)\) 即可。

时间复杂度 \(\mathcal{O}(n^2)\).

F. The Easiest Problem

签到题

G. The squares

题目大意：给你一个集合，元素最大为 \(1000\)，求有多少个非空子集中所有元素的积是完全平方数。答案最大约有 \(10^{300}\)。

题解：

解法一：

朴素想法是直接以每个质数的奇偶性为状态 dp，但是 \(1000\) 内的质数有 \(169\) 个，这样做显然不行。注意到所有大于 \(\sqrt{1000}\) 的质数，一个数中至多只会出现一个，而小于 \(\sqrt{1000}\) 的质数只有 \(11\) 个。因此我们可以以小质数为状态，对于每种大质数分组背包 dp。

时间复杂度 \(\mathcal{O}(2^{11}n\log ans)\)。这个解法复杂度较高，即便在大整数中压 \(18\) 位也基本是卡时限通过的。

解法二(std)：

构造一个模 \(2\) 意义下的矩阵，\(A_{ij}\) 表示 \(a_{i}\) 中第 \(j\) 个质数的奇偶性，答案即为 \(2^{n-rk(A)}-1\)。证明如下：

考虑将矩阵高消，我们可以得到 \(rk(A)\) 个行向量，它们是这 \(n\) 个向量的一组基。我们首先枚举剩余 \(n-rk(A)\) 个 \(a_{i}\) 的取与不取，将它们异或起来就得到了一个行向量。要使最终的和为零向量，我们必须用这组基来表示这一行向量。由线性代数的知识我们知道，有且仅有一种方式能够表示这一行向量。故我们的答案即为 \(2^{n-rk(A)}-1\)。

时间复杂度 \(\displaystyle \mathcal{O}(\frac{169n^{2}}{64})\), 转置再做的复杂度为 \(\displaystyle \mathcal{O}(\frac{169^2n}{64})\)。

H. The fast reading

题目大意：求满足阅读时间不超过 \(n\le10^9\) 秒的由小写字母组成的字符串个数。读一个不为 r 的字母需要的时间固定为 1 秒，但读一个字母 r 的时间取决于 r 前一个字母。

\(1\le A_0, A_1, \cdots, A_{26}\le10\)，分别为 r 前为空，为 a,…,z 的阅读时间。

题解: 令 \(f[n][x]\) 表示阅读时间为 \(n\) ，末尾为 \(x\) 的字符串的个数，则有 \(\mathcal{O}(n\sigma^2)\)。

用矩阵来加速转移，因为 \(A_i\le10\) ，需要记录 \(10\times\sigma\) 个状态，再加一个状态记录和，但是这样复杂度为 \(\mathcal{O}((10\times\sigma)^3\log{n})\)。

注意到 \(f[n][x]\) 中当 \(x\) 不为 \(r\) 的时候，它们所有的转移都是相同的，因此值也一定相同。

因此只需要 \(21\) (\(r\) 和非 \(r\) 两种，2 * 10 + 1， 一个状态累加答案)个状态，可以轻松跑过。

trick: mod 1234567891 时加法会溢出。

I. The best picture

题目大意：一个 \(01\) 串，每位有 \(p\) 的概率是 \(1\)，\(1-p\) 的概率是 \(0\)，求最长的连续 \(1\) 的长度的期望。

题解：设 \(\text{prob}_{i}\) 表示最长的连续 \(1\) 的长度小于等于 \(i\) 的概率，则答案为 \(\sum_{i=1}^{n}i(\text{prob}_{i}-\text{prob}_{i-1})\)。

我们枚举每一个 \(i\)，设 \(\text{dp}[j]\) 表示串长度为 \(j\) 时的答案，则 \(\text{prob}_{i}=\text{dp}[n]\)。我们枚举第一个 \(0\) 出现的位置 \(k\)，则有 \(\text{dp}[j]=p^{j}[j\le i]+\sum_{k=1}^{i+1}(1-p)p^{k-1}\text{dp}[j-k]\)。这个 \(\text{dp}\) 很容易优化到 \(\mathcal{O}(1)\) 转移，可以用滑动窗口，也可以维护一个 \(\displaystyle \frac{\text{dp}[i]}{p^{i}}\) 的前缀和，不过后者由于要做多次乘除法，精度较差。

时间复杂度 \(\mathcal{O}(n^{2})\)。

J. The flowers

题目大意：\(n\) 个节点的树，树上第 \(i\) 个节点初始时有\(F_i\)朵花。\(m\) 天，每天树上每个节点都会增加一朵花，之后会发生以下两种之一的事件：

• 将 \(x\) 节点所有的花摘掉
• 统计节点 \(u\) 和 \(v\) 路径上点的花总数

题解：全局数量为天数 \(t\)，轻重链剖分加树状数组来维护每个点的数量与全局数量不同的部分即可。

时间复杂度 \(\mathcal{O}(n\log^2{n})\).