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\) 次多项式。拉格朗日插值即可。