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