最近做的两道题。

感觉很囧啊，数学全忘了啊。

Google-Codejam-Round3-D

果然 GCJ 滚粗是必然的。

考虑一个事实：在 $i$ 到 $j$ 这一段的一个位置 $k$ ，如果 $k$ 是 . ，那么 $i$ 到 $k$ 和 $k+1$ 到 $j$ 是独立的，即，如果某次一个人进入摩天轮时，他遇到的第一个格子在 $i$ 到 $k$ 之间，那么他最后占领的格子一定会在 $i$ 到 $k$ 中而不会在 $k+1$ 到 $j$ 中。

于是就倒着来思考。首先明显的在最后只剩下一个空的时候，期望是固定的，为 $\frac{n - 1}{2}$ 。

所以我们枚举最后一个空的位置，然后转为序列上的问题。

序列上的问题有明显的子结构：令 $f_{i, j}$ 表示原序列的 $i$ 到 $j$ 这一段，经过若干次操作后，除位置 $j$ 为 . 以外，其余的元素均为 X 的期望代价， $p_{i, j}$ 表示概率。令 $P(i, j, k)$ 表示 $i$ 到 $j$ 这一段， $j$ 一直是 . 的，最后一个转为 X 的 . 的位置为 $k$ ，其余的都是 . 的概率。

$$P(i, j, k) = \binom{Lk + kR}{Lk} (\frac{k+1-i}{j+1-i})^{Lk+1} (\frac{j-k}{j+1-i})^{kR} p_{i, k} p_{k+1,j}$$

其中 $Lk$ 表示初始状态中 $[i, k - 1]$ 中 . 的个数， $kR$ 表示 $[k+1, j-1]$ 中 . 的个数。由于最后一个转为 X 的 . 为 $k$ ，所以我们要考虑到前 $Lk + kR$ 次 X 变 . 的顺序，所以要乘以一个二项式。再乘以有 $Lk + 1$ 个落在 $[i, k]$ 的概率，以及又 $kR$ 个落在 $[k+1,j]$ 的概率，最后乘以合法的概率 $p_{i, k} p_{k+1,j}$ 。

所以得到 $f$ 和 $p$ 的转移如下：

$$\begin{array}{rcl} p_{i, j} & = & \sum_{k = i}^{j - 1} P(i, j, k) \\ f_{i, j} & = & \frac{1}{P_{i, j}}\sum_{k = i}^{j - 1} P(i, j, k) (f_{L, k} + f_{k+1, R} + n - \frac{k-i}{2}) \\ \end{array}$$

注意 dp 时的 $i$ 可能大于 $j$ ，因为这是环状，所有计算长度的公式都需要进行一定的修正。

TopcoderOpen-Round3-Level3

jzp 的神题，我表示被吓傻了……

我还是直接上 传送门 吧……我就写写我的感觉 →_→

主要思想

感觉非常牛逼啊。

1. 用容斥写出答案的表达式
2. 观察这个表达式和 $\Delta^n f(x)$ 很像，于是用 $(-1)^n \Delta^n f(x)$ 来求答案
3. 具体化 $f(x)$ 。如何求 $\Delta^n f(0)$ ？考虑写成 $$f(x) = \sum a_i x^i = \sum b_i \binom{x}{i}$$
4. 可以得到 $$\Delta^n f(0) = b_n$$ 所以求 $b_n$ 就好了……

一些细节

考虑如何求 $b_n$ ？利用

$$x^n = \sum_{k=0}^n k!\stirone{n}{k} \binom{x}{k}$$

可以得到

$$b_n = n! \sum_{k = n} \stirone{k}{n} a_k$$

于是我们只要求 $a$ 就好了。利用

$$\binom{n}{k} = \sum_k \stirtwo{n}{k} (-1)^{n-k} x^k$$

可以拆开一个 $n$ 中含有未知数的二项式。

如何求两类 stirling 数？题目中说了 $m - n \leq 10^3$ ，于是我们要在 $m - n$ 相关的的时间内求出所有涉及到的 stirling 数。假如我们要求 $\stirone{n}{m}$ ，当 $n - m$ 特别小时，考虑 $\stirone{n}{m}$ 的实际意义，表示将 $n$ 个数分成 $m$ 个环的方案数，至多有 $n - m$ 个环的大小不为 1 ，这些环的大小之和至多是 $2(n - m)$ ，于是考虑 $f(i, j)$ 表示 $j$ 个大小大于 2 的环的总大小为 $i$ 的方案数，可以得到一个和 stirling 数类似的递推。