杂题乱做 · jxy

ARC172D

这个题的官方题解是人类能想到的吗？

给一个比较正常的做法。

我们需要构造 $N$ 个点，使得它们之间的 $N(N-1)/2$ 个距离满足给定的严格递增顺序。
使用欧几里得距离公式的展开形式：

d(p_i, p_j)^2 = \|p_i\|^2 + \|p_j\|^2 - 2 p_i \cdot p_j

如果我们强制所有点的模长平方 $\|p_i\|^2$ 为一个常数 $C$ （即所有点位于同一个超球面上），那么距离公式简化为：

d(p_i, p_j)^2 = 2C - 2 p_i \cdot p_j

显然，距离越小，内积（点积）越大；距离越大，内积越小。

因此，问题转化为构造一组向量，使得它们的内积 $p_i \cdot p_j$ 满足与给定距离顺序相反的顺序。可以通过构造一个 Gram 矩阵 $M$ 来实现这一点，其中 $M_{ij} = p_i \cdot p_j$ 。具体的 Gram 矩阵构造方法可以看 https://www.jstor.org/stable/2333639?read-now=1&seq=1

qoj3265

二项式定理告诉我们：

(1 + x)^{nk} = \sum_{m=0}^{nk} C_{nk}^m x^m

我们需要的是 $m \equiv r \pmod k$ 的那些项的系数和。
如果我们在这个多项式环中，定义 $x^k = 1$ ，即在模 $x^k - 1$ 的意义下进行运算，那么：

x^m \equiv x^{m \bmod k} \pmod{x^k - 1}

这意味着， $(1+x)^{nk} \pmod{x^k - 1}$ 展开后的结果中， $x^r$ 的系数正是所有 $m \bmod k = r$ 的 $C_{nk}^m$ 之和。

答案就是多项式 $(1+x)^{nk}$ 在模 $x^k - 1$ 下， $x^r$ 的系数。

直接快速幂一下就做完了。

CF482C

cf482c

对于取值为非负整数的随机变量 $X$ ：

E[X] = \sum_{k=0}^{\infty} P(X > k)

因为最大询问次数为 $M$ ，也就是：

E = \sum_{k=0}^{M-1} P(\text{询问 } k \text{ 次之后仍无法唯一确定目标})

假设我们询问了一个位置集合（用二进制掩码 $mask$ 表示），在这个 $mask$ 下，如果目标字符串 $S_i$ 和另一个字符串 $S_j$ 在所有询问位置上的字符都相同，那么我们就无法区分 $S_i$ 和 $S_j$ 。此时，我们称 $S_i$ 在掩码 $mask$ 下是不可区分的。

定义 $bad_{mask}$ ：当询问集合为 $mask$ 时，不可区分的字符串集合。

然后考虑 SOS dp，

bad_{mask \setminus \{i\}} \ |= \ bad_{mask}

显然，dp 之后，

P(X > k) = \frac{1}{N \cdot \binom{M}{k}} \sum_{|mask|=k} \text{popcount}(bad_{mask})

最终答案即为 $\sum_{k=0}^{M-1} P(X > k)$ 。

qoj9492

显然，问题可以转化为：

每个节点 $u$ 可以映射为一个二维点 $(dfn1_u, dfn2_u)$ 。
$T_1$ 上的路径修改对应于 $dfn1$ 维度上的若干区间加值。
$T_2$ 上的路径查询对应于 $dfn2$ 维度上的若干区间求和。

问题本质上就是二维区域权值维护。由于操作是在线的，且 $N, M$ 较大，直接使用二维线段树或树套树空间和时间开销较大。

我们可以对 $X$ 轴（即 $dfn1$ ）进行分块。

将 $X$ 轴分成 $\sqrt{N}$ 个块。
每个块内部存储该块内的点，并按 $Y$ 轴（ $dfn2$ ）排序。
每个块维护一个懒标记 $tag$ （用于整块加值）和块内点权的前缀和数组（用于快速查询）。

对于每次修改，在 $T_1$ 上通过 HLD 分解为 $O(\log N)$ 个 $X$ 区间。对于每个区间：

若区间完全覆盖某块，更新该块 $tag$ 。
若区间部分覆盖某块，暴力更新块内节点的权值 $A$ ，并重构该块的排序前缀和数组。

对于每次查询，在 $T_2$ 上通过 HLD 分解为 $O(\log N)$ 个 $Y$ 区间。对于每个区间：

遍历所有块。在块内二分到 $Y$ 区间对应的点集，结合前缀和与 $tag$ 计算贡献。

考虑去掉二分。

我们可以维护一个 $cnt_{y,b}$ ，表示在块 $b$ 中， $dfn2$ 值小于等于 $y$ 的节点数量。由于块内节点是按 $dfn2$ 排序的， $cnt_{y,b}$ 的值恰好就是二分到的下标。查询复杂度降为 $O(\frac{N}{B} \log N)$ 。

最优块大小应为 $\sqrt{N} \approx 450$ 。

UOJ574

uoj574

来一个不用动脑子的做法。

原离散概率过程可以等价地转化为连续时间过程。假设每个燃料舱接收燃料的时间间隔服从独立的指数分布，那么第 $i$ 个燃料舱获得第 $k$ 单位燃料的时间 $T_{i,k}$ 服从 Gamma 分布 $\Gamma(k, 1)$ 。
由于选择是均匀随机的，这种连续化模型不会改变事件发生的相对顺序概率。

过程停止的时刻是所有燃料舱都至少有 $b$ 单位燃料。设 $\tau_i$ 为第 $i$ 个燃料舱达到 $b$ 单位燃料的时间，则停止时间

T_{stop} = \max(\tau_1, \tau_2, \dots, \tau_n)

我们关注某一个特定燃料舱（例如燃料舱 1）在停止时是否已满（达到 $a$ 单位）。设 $\rho_1$ 为燃料舱 1 达到 $a$ 单位燃料的时间。如果 $\rho_1 \le T_{stop}$ ，则该燃料舱在停止时已满。
由对称性，期望满舱数 = $n \times P(\rho_1 \le T_{stop})$ 。

我们需要计算 $P(\rho_1 \le \max(\tau_2, \dots, \tau_n))$ 。
利用补集转化： $P(\rho_1 \le M) = 1 - P(M < \rho_1)$ ，其中 $M = \max(\tau_2, \dots, \tau_n)$ 。

P(M < t) = P(\text{所有 } j \in \{2..n\}, \tau_j < t) = (F_b(t))^{n-1}

，其中

F_b(t)

是

\Gamma(b, 1)

的累积分布函数。

已知 $F_b(t) = 1 - e^{-t} \sum_{j=0}^{b-1} \frac{t^j}{j!} = 1 - e^{-t} P_b(t)$ ，其中 $P_b(t)$ 是截断泰勒多项式。

于是我们需要计算：

E[(F_b(\rho_1))^{n-1}] = \int_0^\infty (1 - e^{-t} P_b(t))^{n-1} f_a(t) dt

其中 $f_a(t) = \frac{t^{a-1} e^{-t}}{(a-1)!}$ 是 $\rho_1$ 的概率密度函数。

然后展开 $(1 - e^{-t} P_b(t))^{n-1}$ ：

\sum_{k=0}^{n-1} \binom{n-1}{k} (-1)^k e^{-kt} (P_b(t))^k

我们需要计算 $(P_b(t))^k$ 。由于 $k$ 从 0 到 $n-1$ ，我们可以迭代地计算 $(P_b(t))^k = (P_b(t))^{k-1} \times P_b(t)$ ，这东西能用 NTT 加速。

对于每一项，我们需要计算积分：

\int_0^\infty \frac{t^{a-1} e^{-t}}{(a-1)!} e^{-kt} \left( \sum c_m t^m \right) dt = \frac{1}{(a-1)!} \sum c_m \int_0^\infty t^{a+m-1} e^{-(k+1)t} dt

利用 $\int_0^\infty x^N e^{-\lambda x} dx = \frac{N!}{\lambda^{N+1}}$ ，上述积分变为：

\frac{1}{(a-1)!} \sum c_m \frac{(a+m-1)!}{(k+1)^{a+m}}

总复杂度为 $\sum O(kb \log(kb)) \approx O(n^2 b \log(nb))$ 。