可以观察样例发现规律，对于每一条加进来的边$(u, v)$，如果$u, v$连通，则$ans = ans \times 2 -1(ans = 1 when init)$，不连通就连边即可，显然用并查集维护。

有一个易懂的证明：
题目中每个点的度数大于零且都是偶数的子图等于这个子图就是几个环(它们之间不一定连通)，对于每一条加进来的边$(u, v)$，如果$u, v$连通，那么$(u, v)$连上以后会形成一个环。而如果有一条路径$L$连接$u,v$，那么可以用边$(u, v)$替换掉$L$，则之前的每个方案都可以替换，那么答案自然就多一倍了。

Codeforces 540D
设$dp(i,j,k)$为石头有$i$人，剪刀有$j$人，纸有$k$人的状态存在的概率。
则转移方程为
$$dp(i,j,k)= dp(i+1,j,k) \times P_1 + dp(i,j+1,k) \times P_2 + dp(i,j,k+1) \times P_3$$
$dp(r, s, p) = 1.0$
但是这样不好转移，因为概率是很难算的，那我们改一下原方程：
设$sum=ij+ik+jk$
$dp(i-1, j, k)=dp(i, j, k) \times \frac{ik}{sum}​$
$dp(i, j-1, k)=dp(i, j, k) \times \frac{ij}{sum}​$
$dp(i, j, k-1)=dp(i, j, k) \times \frac{jk}{sum}​$
这样就方便转移了，最后的答案累加一下必胜的状态的存在概率即可。

把所有地鼠按消失时间$t$排序，然后维护一个小根堆，每次不断地插入，直到当前时间大于插入的时间，那就把堆顶拿出来比较，如果小于当前的，就替换掉。

zoj 3640
设$dp(u)$为力气值为$u$时的逃离期望。
当$u \leq c(i)$时可以转移到$dp(u+c(i))$，否则$dp(u)$可以直接加上$t(i)$
显然记忆化搜索好写，直接写记忆化搜索即可，递推其实也可以的。

知识点讲解

排列组合

圆周排列
从$n$个不同元素中无重复地取出$k(1≤k≤n)$个元素排在一个圆周上，称为$n$个不同元素的一个圆周排列，简称k-圆排列
圆周排列个数为
$$\frac{A^k_n}{k} = \frac{n!}{k\cdot(n-k)!}$$

poj 2151
设$dp(i, j, k)$为选手$i$在前$j$题中做对$k$题的概率，则转移方程为
$$dp(i,j,k)=dp(i,j-1,k-1) \times p(i,j) + dp(i,j-1,k) \times (1-p(i,j))$$
初始化的时候$dp(i,0,0)=1, dp(i,j,0)=dp(i,j-1,0) \times (1-p(i,j))$
然后因为我们要求出所有选手做对一题且有选手做出大于等于$n$题，所以这是个容斥问题，即可以用所有选手至少做对一题的概率$P_1$减去所有选手做对题目个数在$[1, n-1]$之间的概率$P_2$的差即为答案，怎么求呢？
设$s(i,j)$为选手$i$做对至多$j$题的概率，则$s(i,j)= \sum_{k=0}^{j} dp(i, k)$
则$P_1= \prod_{i=1}^{t}(1-s(m, 0)) $
$P_2= \prod_{i=1}^{t}(s(m, n-1)-s(m, 0)) $
$P_1 - P_2$即为答案(容斥原理)

Codeforces 148D
设$dp(i, j)$为轮到王妃选鼠的时候白鼠有$i$只，黑鼠有$j$只时赢的概率。
分4种情况.
1、王妃选到白，则概率为$\frac{i}{i+j}$
2、龙选到白，王妃输了，则概率为$0$
3、王妃选到黑，龙选到黑，逃了黑，转移到$dp(i, j-3)$，则概率为$\frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{j-2}{i+j-2}$
4、王妃选到黑，龙选到黑，逃了白，转移到$dp(i-1, j-2)$，则概率为$\frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{i}{i+j-2}$
那么综上所述可以得到状态转移方程
$dp(i,j) = \frac{i}{i+j} + \frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{j-2}{i+j-2} \times dp(i, j-3)+\frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{i}{i+j-2} \times dp(i-1, j-2)$
注意不要一起乘，不然溢出。

hdu 4405
设$dp(i)$为$i$到$n$的步数期望。
则
$$dp(i) = \sum \frac{1}{6}dp(i+j)$$
其中$i+j \leq n+5$或者$i+j \leq n$。如果$i$处有航线，那么直接$dp(i) = dp(lst(i))$
答案为$dp(0)​$

hdu 3853
设$dp(i,j)$为$(i,j)$到$(r,c)$的步数期望，那么可以列出下列状态转移方程：
$$dp(i,j)=\frac{dp(i,j+1) \times P_2 + dp(i+1,j) \times P_3}{1-P_1}$$
但是当$P_1=1$时，$dp(i,j)=0$，因为这个点肯定无法到达终点，设为$0$表示该点不影响其他点。

BZOJ 1715
Luogu 2850
from: USACO 2006 Dec Gold
由题意就是判一个负环，用SPFA，据说DFS要快一点，不过这里还是BFS了。
一个点进队超过$n$次就存在负环。