OI

LibreOJ #138 类欧几里得算法

题意

$T \leq 1000$ 组数据。给定 $n, a, b, c\in [0, 10^9], k_1,k_2\in [0, 10], k_1+k_2\leq 10$，求取 $$\sum_{x=0}^{n}x^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}$$

部分分——观察性质

当 $k_1=0,k_2=1$ 时，是为一般类欧几里得算法的模板。上述链接亦给出了 $k_1=0,k_2=2; k_1=1,k_2=1$ 时的解法。

当 $k_2=0$ 时，该式退化为 $\sum_{x=0}^{n}x^{k_1}$，即 $k_1$ 次的等幂求和。有一个模糊的结论：

设 $n$ 为正整数。则$k$ 次的等幂求和，$\sum_{x=0}^{n}x^k$，是一个关于 $n$ 的 $k+1$ 次多项式。

该结论来源于 zyw 学姐多项式专题所选题目 BZOJ 3453 – tyvj 1858 XLkxc。之所以说模糊，是因为该多项式的系数是已知的。不过我们仍然可以暴力计算 $k+2$ 个点以插值。

再观察 OI-Wiki 上对于 $k_1+k_2\leq 2$ 时的解法。在求取 $$h(n,a,b,c)=\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2$$时采取了如下转化：

$$\begin{aligned} x^2&=2\times \frac{x(x+1)}{2}-x\\ &=2\left(\sum_{y=1}^{x}y\right)-x\end{aligned} \quad\begin{aligned} \Longrightarrow\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2=\sum_{x=0}^n2\left(\sum_{y=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}y\right)-\left\lfloor\frac{ax+b}{c}\right\rfloor\\ \end{aligned}$$

这样一来，由于 $y$ 是一个线性算子，在 $ax+b\geq yc$ 时都有 $y$ 向总和贡献，于是我们可以应用类似于 $k_1=0,k_2=1$ 时的方法转化贡献。这个过程对 $k_2$ 作了降次。

那么，对于更高次项，有无办法采取同样的办法转化呢？是否可以设计一些转化，使得要求取的函数 $f(\cdots,k_1,k_2)$ 能够由 $f(\cdots,k_1-?,k_2-?)$ 推出呢？ （更多…）

形式化题意

给定 $A+B$ 个本质相同的随机变量，在 $\{1,2,\cdots,6\}$ 内等概率取值。若两个随机变量 $a \in A, b \in B, a=b$，则二者相消为 $0$。求在所有可能的消除完成后，存在 $a \leq t, a \in A, t \in \{1,2,\cdots,6\}$ 的概率。对 $10^9+7$ 取模。

朴素DP

令 $c_i$ 表示随机结果中数值为 $i$ 的 $A$ 内变量数；$d_i$ 同理。原题意可以转化为求出 $1-P(\text{不存在小于等于}t\text{的}a)$。由概率的定义，我们可以用能造成后者局面的方案总数除以 $6^{A+B}$ 既是结果。换句话说，原命题的否命题应当满足 $\forall i \in \{1,2,\cdots,t\}, c_i \leq d_i$。

又因为这些随机变量本质相同，则由“可重集的排列数”得，若有确定的 $c_{1},c_2,\cdots,c_6, \sum_{i=1}^{6}c_i=A$，则掷出对应结果的方案数为 $$\dbinom{A}{c_1}\dbinom{A-c_1}{c_2}\cdots\dbinom{A-\sum_{i=1}^{5}c_i}{c_6}=\dfrac{\color{blue}A!}{\prod_{i=1}^{6}c_i!}$$ （更多…）

CodeForces Round #502 Problem G – The Tree

这是lty数据结构专题里唯二自己做出来的题目中的一道。

如果不包含“将 $x$ 的子树全部染白”的操作，应当怎样处理？

题目所给操作可以这样转述：令 $x$ 为本次染色操作的节点。若 $x$ 为白色，则立刻染黑并退出；否则我们找到其子树中的，与 $x$ 相连的黑色连通块，则对于每个连通块底部节点，若其不是叶子节点，我们将其儿子染黑。

由于本题的树没有特殊性质，且将来加入回退操作，故而难以维护整个连通块以及其叶子节点。因此，我们可以从“在何种情况下，节点 $x$ 被染黑”的方向考虑。

显然，只有从在 $x$ 到根的路径上的节点开始的染色操作，才可能波及到 $x$。假如最终 $x$ 被染黑的一瞬，它被包含在了以 $\text{comprt}$ 为根的连通块中。令链 $\langle\text{comprt}, x\rangle$ 为 $\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x$，那么自然想到，一种一定合法的染色序列是 $\{y_1,y_2,\cdots,y_n\}$，其中有 $\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\}$，也即我们每一步都在该连通块内部，并将连通块的最大深度推进一层。

这种序列确实合法（它是充分条件），但这真的是 $x$ 被染黑的必要条件么？ （更多…）