CF963E Circles of Waiting
圆内的整点形成了一个类似方阵的结构。设$f_{x,y}$为$(x,y)$期望被经过的次数。我们可以对每一个点列出一个方程：
将每一行最左侧的点设为主元，其它的点都用主元表示。从左往右考虑每一列的点：$f_{x,y}$可以用$f_{x-1,y}$的方程表示出来（因为方程中涉及到的$f_{x-1,y},f_{x-1,y-1},f_{x-1,y+1},f_{x-2,y}$在之前都已经考虑过了，只有$f_{x,y}$是未知的）。
这样过后，每一行最右侧的点对应的方程我们还没有用过，用这些方程一定可以解出主元的值，然后再带回去就可以得到每个点的期望被经过次数。
时间复杂度$O(R^3)$。
CTSC2006 歌唱王国
题号：luogu4548, bzoj1152
设$f_i$为加入第$i$个字符的时候恰好结束的概率，$g_i$为加入$i$个字符之后还没有结束的概率。设$F(x) = \sum_{i=0}^\infty f_i x^i, G(x) = \sum_{i=0}^\infty g_ix^i$。
则有$G(x)x - F(x) = G(x) - 1$，即：$g_{i-1}-f_i = g_i$。
由$F(x)$的定义我们知道$F(1)=1$，即在每一轮结束的概率的和是$1$。
而我们要求的答案是$F’(1)$。
再设$H(x) = \sum_{i=j}^{m}x^{m-j} ({1\over n})^{m-j} [s_1s_2\cdots s_j\text{is a border of s}]$。
则
这里$F(x)$的意义相当于是枚举了，$G(x)$在末尾加上一个$s$之后，最早在什么位置出现了完整的$s$。
带入$x=1$得到
此外
两边同时求导得到
带入$x=1$
所以答案就是$n^m H(1)$。
PE522
如果所有的连通块都是孤立的环（没有叶子），那么答案是环数。
否则敲定一个不为孤立的环的连通块，对于这个连通块每一个入度为$0$的点，把某个入度大于$1$的点的某一个儿子拿过来接在它的下面（接过来的部分如果还有入度为$0$的点，就重复前面的操作）。
如果图内存在孤立的环，就还必须在上述过程的最后一次操作之前（此时我们敲定的那个连通块内恰好只有一个叶子）对每一个孤立的环进行额外的操作：把环断成链接在叶子的下面。
综上所述，一张图的答案为叶子数+孤立的环数。
叶子数总和为：
也就是每个点成为叶子的方案数。
孤立的环的数量总和为
每一个长度为$i$的环出现的方案数是$(n-i-1)^{n-i}$，而这样的环有${n\choose i} \cdot (i-1)!$个。
CF457D Bingo!
考虑$2^s$的组合意义，也就是一个大小为$s$的集合的子集数量。所以权值的期望也就是：每一个行、列的子集在最后的矩阵中只包含了那$k$个数的概率的和。
假设某一个子集包含了$t$个格子，那么它只包含了那$k$个数的概率是$f_t = {P_k^t \over P_m^t}$。直接预处理阶乘来计算$f_t$无法用long double存下；推导可得$f_t = f_{t-1} \cdot {k-t+1\over m-t+1}$，由这个递推计算就可以避免上面的问题。
最后的答案就是
UOJ352 新年的五维几何
对于所有$l_i=r_i$的变量，考虑它们对其它变量的取值范围的影响，然后把这些变量删掉。
不妨将$l_i \le x_i \le r_i$看做$l_i \le x_i < r_i$，两者算出来的答案是一样的。所以$x_i$的整数部分的取值范围是$[l_i,r_i)$。
我们首先枚举$x_i$的小数部分的大小关系，然后暴搜整数部分的合法的取值方案。由于$a_{i,j}$都是整数，所以$x_i - x_j \ge a_{i,j}$是否被满足只取决于$x_i$和$x_j$的整数部分和它们小数部分的大小关系。
时间复杂度$O(n!\prod_i(r_i-l_i))$。