2022.1.18

So hard ！

zzz 怎么挑了套如此困难的题！

小 Y 和恐怖的奴隶主

$11$ 分的 $dp$ 不难写出。

记录 $f[i][a][b][c]$ 为攻击 $i$ 下，场上有 $a$ 个一血怪， $b$ 个两血怪， $c$ 个三血怪的概率。

期望即对每一层 合法的 $f[i]$ 求前缀和。

考虑到我们攻击次数实际上并无实际用处， 每次进行的操作都一样，只是重复了 $10^{18}$ 次。

进而我们可以使用矩阵乘法优化。

好像还是过不去， 利用快速幂的思想优化， 预处理二的整次幂的次方的矩阵， 询问时可以降一个状态的复杂度。

跳跳棋

可怕的建模 ！

考虑我们只有三种不同的跳法。

1 $b$ 越过 $a$

2 $b$ 越过 $c$

3 $a$ 越过 $b$ 或 $c$ 越过 $b$

由于我们最后求的是相对位置， 发现进行 $1$ 和 $2$ 操作的时候边界会扩大， 进行 $3$ 操作边界会缩小。

在 $b - a = c - b$ 的时候就无法再进行移动。

因此不妨看作扩大边界为两个儿子， 缩小边界为父亲，这样就将操作一一对应上。

问题转化为两个节点在树上需要几次到达，也就是求树上距离问题。

我们接着发现， 在 $3$ 操作向里面缩的时候，在允许范围内每次缩的结果是相同的，因此我们可以将相同的操作压缩起来，一次进行若干次向上跳父亲的操作来减小复杂度。

最后 二分到两点深度相同的地方， 在一同向上跳到 $lca$ 处即可。

Calc

考虑 钦定填的数字递增， $f(n,i)$ 为前 $n$ 位用 $1-i$这些数字的总价值。

转移为

$f(n,i)=f(n-1,i-1)\times i+f(n-1,i)$

乘上阶乘即可。

看起来 $f(n,i)$ 是关于 $i$ 的多项式。

假设 $f(n,i)$ 关于 $i$ 的 $g(n)$ 次多项式。

观察到有差分的形式

$f(n,i)-f(n-1,1)=f(n-1,i-1)\times i$

不难发现左边是关于 $i$ 的 $g(n)-1$ 次多项式，右边是 $g(n-1)+1$次多项式

因此

$g(n)=g(n-1)+2$

显然有

$g(0)=0$

因此这就是关于 $i$ 的 $2n$ 次多项式。拉格朗日插值即可。