T1
假设有 \((x,y)\) 表示 \(x\) 个瓜子 \(y\) 个皮,显然有 \(x/(x+y)\) 概率转移到 \((x-1,y+2)\),和 \(y/(x+y)\) 概率转移到 \((x,y-1)\)。连线后成为了一个 DAG。
记 \(dp_{x,y}\) 表示从 \((x,y)\) 状态到达终点 \((0,2n)\) 的期望,可以用记忆化搜索实现 dp 过程。
T2
对于每个位置 \(i\),钦定他就是第 \(k\) 大,也就是说区间中有 \(k-1\) 个比它大的。如果 \(1 \sim (i-1)\) 有 \(x\) 个,\((i+1) \sim n\) 就有 \(k-1-x\) 个。也就是说,对于每个 \(i\),我们需要知道它前后第 \(j\) 个大于等于 \(a_i\) 的下标。例如序列 5 3 1 2 4
的 \(3\) 前面有 1
,后面有 5
。
我们可以把序列排序后,维护一个链表。一开始链表为 1-2-3-4-5
,后来的每一个数都从链表上删掉一些节点。还是以 5 3 1 2 4
举例,排序后为 1 2 3 4 5
,枚举到 \(3\) 时链表就变成了 1-5
。
知道怎么维护后,答案就成了对于每个位置往左找 \(i\) 个比它大的,往右找 \(k-1-i\) 个比它大的。假设找到的最左边和最右边为 \(L,R\),而找到左边第 \(i-1\) 个和右边 \(k-1-i-1\) 个比它大的为 \([L',R']\),则如果区间 \([l,r]\) 满足 \(L'<l\le L,R \le r < R'\),这个区间就满足条件。计数即可。