尽可能尝试写出一个式子。

我们不妨设 \(f_{i}\) 表示走到 \(i\) 的期望步数。
怎么转移来？有两种可能，从 \(i-1\) 走一步过来，这个的概率是 \(1-P_{i}\)，走了 \(f_{i-1}+1\) 步。
第二种是掉回起点重新走过来，概率是 \(P_{i}\) 这样需要走 \(f_{i-1}+1+f_{i}\) 步。
于是我们便可以写出一个式子长这样 \(f_{i}=(f_{i-1}+1)(1-P_{i})+(f_{i-1}+1+f_{i})P_{i}\)。
我们来化简一下：

\[ \begin{aligned} f_{i}&=(f_{i-1}+1)(1-P_{i})+(f_{i-1}+1+f_{i})P_{i}\\ f_{i}&=f_{i-1}+1-f_{i-1}P_{i}-P_{i}+f_{i-1}P_{i}+P_{i}+f_{i}P_{i}\\ (1-P_{i})f_{i}&=f_{i-1}+1\\ f_{i}&=\dfrac{f_{i-1}+1}{1-P_{i}} \end{aligned} \]

非常的 amazing 啊，我们就成功地推出了式子。
因此，以后先大胆写出式子，看看能不能转化一下，推导出正确式子。

先想想 \(n\) 比较小的时候怎么做。

不难想到设计状态 \(f_{i,j}\) 表示第 \(i\) 个视频发第 \(j\) 种类型后的期望分数。转移是容易的 \(f_{i,j}=\dfrac{\sum\limits_{k=1}^{t}f_{i-1,k}d_{k,j}}{t}\)。
但是我们要求的是收益，于是再设 \(g_{i,j}\) 表示第 \(i\) 个视频发布第 \(j\) 种类型后的期望收益，容易得到 \(g_{i,j}=\dfrac{\sum\limits_{k=1}^{t}g_{i-1,k}}{t}+f_{i,j}b_{j}\)。

至此你得到了一个 \(O(nt^3)\) 的做法，可以获得 \(15\) 分，继续优化。

我们设 \(ans_{i}=\dfrac{\sum\limits_{j=1}^{t}g_{i,j}}{t}\) 也就是发布第 \(i\) 个视频后的总收益期望。
我们发现先前的式子可以简写成 \(g_{i,j}=ans_{i-1}+f_{i,j}b_{j}\)。我们显然要从 \(ans_{i-1}\) 推到 \(ans_{i}\)。

\[ \begin{aligned} ans_{i}&=\sum_{j=1}^{t}\dfrac{ans_{i-1}+f_{i,j}b_{j}}{t}\\ &=ans_{i-1}+\dfrac{\sum\limits_{j=1}^{t}f_{i,j}b_{j}}{t} \end{aligned} \]

最后的答案显然是 \(ans_{n}\)。

至此，我们的复杂度为 \(O(nt^2)\)。可以获得 \(32\) 分（不算特殊性质之类的。）
还能怎么优化？注意到 \(n\) 很大。

考虑矩阵快速幂优化，我们可以写出这么一个矩阵：

\[ \begin{bmatrix} f_{i-1,1}&f_{i-1,2}&\cdots&f_{i-1,t}&sum_{i-1}\\ \end{bmatrix}\times \begin{bmatrix} \dfrac{d_{1,1}}{t}&\dfrac{d_{1,2}}{t}&\cdots&\dfrac{d_{1,t}}{t}&\dfrac{\sum_{j=1}^{t}d_{1,j}b_{j}}{t^2}\\ \dfrac{d_{2,1}}{t}&\dfrac{d_{2,2}}{t}&\cdots&\dfrac{d_{2,t}}{t}&\dfrac{\sum_{j=1}^{t}d_{2,j}b_{j}}{t^2}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ \dfrac{d_{t,1}}{t}&\dfrac{d_{t,2}}{t}&\cdots&\dfrac{d_{t,t}}{t}&\dfrac{\sum_{j=1}^{t}d_{t,j}b_{j}}{t^2}\\ 0&0&0&0&1\\ \end{bmatrix}\\= \begin{bmatrix} f_{i,1}&f_{i,2}&\cdots&f_{i,t}&sum_{i}\\ \end{bmatrix} \]

我们重点讲解一下最后一列前 \(t\) 项。

我们将上一个 Hint 中的转移式子继续展开。（把 \(ans_{i-1}\) 先扔了）

\[ \begin{aligned} &\dfrac{\sum\limits_{j=1}^{t}f_{i,j}b_{j}}{t}\\ =&\dfrac{\sum\limits_{j=1}^{t}b_{j}\sum\limits_{k=1}^{t}f_{i-1,k}d_{k,j}}{t^2}\\ =&\dfrac{\sum\limits_{k=1}^{t}b_{k}\sum\limits_{j=1}^{t}f_{i-1,j}d_{j,k}}{t^2}\\ =&\sum\limits_{j=1}^{t}f_{i-1,j}\left(\dfrac{\sum\limits_{k=1}^{t}b_{k}d_{j,k}}{t^2}\right)\\ \end{aligned} \]

后面的括号中将 \(j\) 从 \(1\) 枚举到 \(t\) 的时候便依次是矩阵中的那 \(t\) 项。

时间复杂度 \(O(t^3\log n)\)，可以通过。
注意一下 \(n=1\) 的时候特判一下，以及开始是 \(v\) 不是 \(1\)。

期望有这么一个式子 \(E(x)=\sum_{i\ge 1}P(i>x)\)，对于这道题，\(P(i>x)\) 也就是 \(i\) 轮后依然存活的概率，\(n\) 很小，不妨暴力一点。

考虑一个容器什么时候必然会被击倒，再尝试计算一下。

我们先预处理对于每一个位置前面第一个比其强的，以及后面第一个比其强的。
不难发现，我们要存活 \(a\) 轮，必须决斗 \(a\) 次，决斗又可能是其到前面第一个比其强的之间的某两个，也有可能是其到后面第一个比其强的之间的某两个，也又可能是除了这两个区间的某两个。
假设到前面的第一个比其大的位置可以合并 \(x\) 次，后面的可以合并 \(y\) 次，那么剩下的有 \(n-1-x-y\) 次。不难得到合法方案数为：

\[ a!\sum_{i+j+k=a,0\le i\le x,0\le j\le y,0\le k}\binom{x}{i}\binom{y}{j}\binom{n-1-x-y}{k} \]

总的方案数不难算出是 \(\binom{n-1}{a}a!\)，两者一除便是存活 \(a\) 轮的概率，最后加起来便是该点的答案。

找前面第一个比其强的可以使用单调栈，但我们后面都是 \(O(n^4)\) 的了，这里暴力就行。

ps：此题有 \(O(n)\) 做法，但涉及到生成函数或是较复杂的容斥，这里不作展开。

\(E(x^3)=E(x)^3\) 吗？显然不等于，因为 \(x\) 和 \(x^2\) 之间并不是相互独立的。

注意到每次贡献只会有 \(1\)。

我们计算一下对贡献的增量。

\[ \begin{aligned} &E((x+1)^3)\\ =&E(x^3+3x^2+3x+1)\\ =&E(x^3)+E(3x^2)+E(3x)+E(1)\\ =&E(x^3)+3E(x^2)+3E(x)+1\\ \end{aligned} \]

于是我们只需要额外维护 \(E(x^2)\) 和 \(E(x)\) 即可，\(E(x^2)\) 维护是类似的。

时间复杂度 \(O(n)\)。

先不考虑修改，怎么算？

不难发现，因为是线段树，所以每个点走到的概率始终是 \(\dfrac{1}{2}\)。我们定义深度为该节点在线段树上到根节点的距离，那么对于深度相同的，每个点到达的概率是相同的，直接将一行的和加起来乘上概率即可。
接着不妨考虑一下增加后的贡献，可以把线段树的样子画出来看看。

我们以 \(n=5\) 为例，考虑每个位置的贡献，我们发现其会对从叶子节点到根的整条路经产生贡献。并且概率依次是 \(1,\dfrac{1}{2},\dfrac{1}{4},\cdots,\dfrac{1}{2^{dep_{i}}}\)。加起来的和显然是 \(2-\dfrac{1}{2^{dep_{i}}}\)。那么一个点增加 \(val\) 的权值，产生的贡献也就是 \(val\times(2-\dfrac{1}{2^{dep_{i}}})\)，而区间加，也就是 \(val+\sum\limits_{i=l}^{r}\left(2-\dfrac{1}{2^{dep_{i}}}\right)\)。容易发现这个可以用前缀和快速求出。
时间复杂度 \(O(n\log{n}+m)\)。

有一道加强版，你们可以自行思考一下：P4927 [1007] 梦美与线段树

有向无环图怎么做？

不难想到，我们先求出每条边期望经过次数，贪心的标号，经过次数多的标小的号。
那么问题就变成如何求每条边的期望经过次数。

不难想到，对于一条边，其期望经过次数和两端的点有关，假设分别为 \(u\) 和 \(v\)，\(f_{i}\) 表示 \(i\) 这个点的期望经过次数，\(d_{i}\) 表示 \(i\) 这个点的度数，那么这条边期望经过次数显然为 \(\dfrac{f_{u}}{d_{u}}+\dfrac{f_{v}}{d_{v}}\)。

那么对于有向无环图，我们只需要拓扑排序一下，便可以简单的求出每个点的期望经过次数。
但是我们发现无向图可能会走过来走过去，这个该如何处理？不妨还是尝试写出式子。

类似于有向图，我们发现与 \(u\) 这个点相邻的所有点都可以转移到 \(u\)，也就是：

\[ f_{u}=\sum_{v}\dfrac{f_{v}}{d_{v}} \]

这个诈一看感觉不可求，实际上，我们将每个点的方程都列出来。发现这是一个 \(n\) 元方程组，并且恰好有 \(n\) 个方程。
于是我们便可以使用高斯消元来求出每个 \(f_{i}\) 的值，剩下的便和前面一样了。ljx 说给你们讲过高斯消元了，我这里就不再赘述。

注意对于 \(n\) 号点要特殊处理，因为走到 \(n\) 后就不会再走了。

是不是感觉有点眼熟？

和 T1 很像对吧，不妨也类似的写出式子。

类似 T1，我们令 \(dp_{i}\) 表示走到 \(i\) 所需的期望步数。 根据期望的线性性，从 \(i\) 走到 \(j\) 所需的期望步数也就是 \(dp_{j}-dp_{i}\)。

\[ \begin{aligned} dp_{i}&=\dfrac{dp_{i-1}+1}{d_{i-1}}+\sum_{u}\dfrac{dp_{i}-dp_{u}+dp_{i-1}+1}{d_{i-1}}\\ &=dp_{i-1}+1+\dfrac{(d_{i-1}-1)dp_{i}}{d_{i-1}}+\sum_{u}\dfrac{-dp_{u}+1}{d_{i-1}}\\ &=dp_{i-1}+\dfrac{(d_{i-1}-1)dp_{i}}{d_{i-1}}+1-\sum_{u}\dfrac{dp_{u}}{d_{i-1}}\\ \dfrac{dp_{i}}{d_{i-1}}&=dp_{i-1}+1-\sum_{u}\dfrac{dp_{u}}{d_{i-1}}\\ dp_{i}&=dp_{i-1}d_{i-1}+d_{i-1}-\sum_{u}dp_{u}\\ \end{aligned} \]

照着式子做就行了。

假如对于1 2 1 2这么个数组，假如你现在在求 \(i=4\) 的答案，在第 \(4\) 个位置失配了，并不会完全重新匹配，而是会继续从第 \(2\) 个点继续匹配。
你想到了什么。

发现这个过程十分类似于 KMP，一个位置失配了不会重新匹配，而会从其在 KMP 上的 Fail 指针处继续跳。
发现这非常类似于上一道题的返祖边操作，可以选择每个点最多会往回连 \(N\) 条边，但是会爆炸。而且对于 Fail 指针的 Fail 指针也会出现一定的问题。怎么处理这些问题。

首先，我们并不需要真正的连 \(N\) 条边，对于前面的影响我们也可以从前往后写出式子来消元之类的来处理。
你们可以自行尝试一下这个做法，我这里介绍一个更加巧妙的做法。

我们先对单独一个前缀求答案，假设这个前缀为 \(S\)。
每个时刻可以支付 \(k\) 元来猜下一个位置是哪个字符，猜对了返还 \(Nk\) 元。（\(N\) 为字符集大小）
显然这个的期望是 \(Nk/N-k=0\)。

我们现在有若每一时刻有一个新的人来猜，每个人都会按照 \(S\) 的顺序来猜，每个人初始都有 \(1\) 元，假如其猜中了，其会将得到的所有钱 \(N\) 来猜 \(S\) 的下一个字符；如果输了，他就会离开。

在某一时刻，假如这个时刻是 \(M\)，某个人 \(i\) 将这个 \(S\) 猜完了，此时显然这个 \(M\) 就是答案。这个人 \(i\) 获得了 \(N^{\left|S\right|}\) 元，除了这个人，还有人获得钱，比如121这个串，显然第 \(i+2\) 个人最后猜中了 \(1\) 这个字符，我们发现，有猜中的人都是 \(S\) 的公共前后缀，这个是可以简单的由 KMP 求出。

因为我们前面证明了期望是 \(0\)，说明这些人赚的钱，都是从前面所有的人输掉的钱得来的，每个人初始又只有 \(1\) 元，也就说明 \(M=N^{\left|S\right|}+\cdots\)。

所以我们对于一个前缀，只需要一直跳 Fail 指针，即可求出答案。而对于其他前缀，我们设 \(f_{i}\) 表示 \([1,i]\) 这个前缀的期望。可以得到 \(f_{i}=f_{Fail_{i}}+N^{i}\)。

时间复杂度 \(O(M\log M)\)。