51nod1836.战忽局的手段

题目链接

题意

众所周知，有一个神秘的组织——战忽局，在暗中保护着我们。在局中任职的官员都有着极强的忽悠技巧，不只能用预言，还能用往事忽悠人。如今某外星间谍已经获得了战忽局曾经参与的$n$次事件的资料，局座发现了这件事，于是决定再次用忽悠来保证战忽局的安全。局座将发表$m$次演讲，每一天他都会从$n$事件中等概率地挑选一件混淆众人，由于局座每天很忙，不能把之前将的事件都记录下来，因此他可能会重复选择某一件事。现在局座想知道，$m$次演讲过后，期望能使多少事件混淆众人。

输入输出和数据范围

第一行一个正整数$T(1 \leq T \leq 1000)$， 表示数据组数。 接下来$T$行每行两个正整数$n, m(1 \leq n, m \leq 10^{18})$

每组数据输出一个实数$ans$， 与标准答案误差不超过$10^{-6}$即视为正确

题解

由题面数据范围不难看出这次采用的应该是$O(log)$的算法， 那我第一感觉是快速幂(这题解法可以说是快速幂但又完全不是)

既然是期望$dp$， 那我们就按照常规的方法设$dp$数组， 之后再尝试化简合并

设$dp[i][j]$表示局座演讲了$i$次， 使$j$个事件混淆众人的概率

显然对$i > 0, j > 0$有

$$dp[i][j] = d[i - 1][j] \times \frac{j}{n} + dp[i - 1][j - 1] \times \frac{n - (j - 1)}{n}$$

另设$g[i]$表示$n = i$时的答案(方便一会合并用)

接下来我们开始化简

$$g[i] = \sum_{j = 1}^i f[i][j] \times j$$ $$= \sum_{j = 1}^i f[i - 1][j] \times \frac{j^2}{n} + \sum_{j = 1}^i f[i - 1][j - 1] \times \frac{j \times (n - (j - 1))}{n}$$

上式的前半部分， 当$j = 0$和$j = i$时$f[i - 1][j] \times \frac{j ^ 2}{n}$显然为零， 添加或减少这两项对和式的值没有影响

后半部分，对$j$进行抖动

$$= \sum_{j = 0}^{i - 1} f[i - 1][j] \times \frac{j ^ 2}{n} + \sum_{j = 0}^{i - 1}f[i - 1][j] \times \frac{(j + 1) \times (n - j)}{n}$$ $$= \sum_{j = 0}^{i - 1} f[i - 1][j] \times \frac{n \times j + n - j}{n}$$ $$= \sum_{j = 0}^{i - 1} f[i - 1][j] \times (j \times \frac{n - 1}{n} + 1)$$ $$= \frac{n - 1}{n} \times g[i - 1] + \sum_{j = 0}^{i - 1} f[i - 1][j]$$ $$= \frac{n - 1}{n} \times g[i - 1] + 1$$

我们就得到了

$$g[i] = \frac{n - 1}{n} \times g[i - 1] + 1$$

一旦$n$确定了， $\frac{n - 1}{n}$就变成了一个常数， 那么这个递推式就可以写成矩阵乘法的形式了！

显然我们的转移矩阵需要两维

初始矩阵为

$$\begin{pmatrix} g[i] & 1 \end{pmatrix}$$

转移矩阵为

$$\begin{pmatrix} \frac{n - 1}{n} & 0 \\ 1 & 1 \end{pmatrix}$$

但是题解说由于$\frac{n - 1}{n}$是实数， 精度损失会很大， 大概只能有$10^{-2}, 10^{-3}$的样子， 所以要使用高精度