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'\)，这个区间就满足条件。计数即可。