Google-Codejam-Round3-D-and-TopcoderOpen-Round3-Level3
最近做的两道题。
感觉很囧啊，数学全忘了啊。
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
\(\newcommand{\stirone}[2]{\left\{ { #1 } \atop { #2} \right\} }\) \(\newcommand{\stirtwo}[2]{\left[ { #1} \atop { #2} \right] }\) jzp 的神题，我表示被吓傻了……
我还是直接上 传送门 吧……我就写写我的感觉 →_→
主要思想
感觉非常牛逼啊。
- 用容斥写出答案的表达式
- 观察这个表达式和 \(\Delta^n f(x)\) 很像，于是用 \((-1)^n \Delta^n f(x)\) 来求答案
- 具体化 \(f(x)\) 。如何求 \(\Delta^n f(0)\) ？考虑写成 \[f(x) = \sum a_i x^i = \sum b_i \binom{x}{i}\]
- 可以得到 \[\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 数类似的递推。