Charles Wu的博客

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!}$$ （更多…）