poj 3071
题意：有$2^n​$个队进行$n​$轮比赛，每轮比赛相邻(例如1-2, 3-4, 5-6)的两个队比赛一场，给出胜率矩阵，求出哪个队最大几率获胜。
设$dp(i,j)$为第$i$轮比赛$j$赢的概率。
$dp(i,j)=\sum dp(i-1, j) \times dp(i-1, k) \times p(j, k)$ (全概率公式)
其中$k$是和$j$相邻的队。
通过分析队编号的二进制(从0开始),可以发现(j>>(i-1))^1)==(k>>(i-1)的时候$k$和$j$相邻，具体可以自己推一推。

此题在线做很麻烦，而且这题也不强制在线，不会修改$A$的值，那就离线吧。
先求出$[1, i]$的$mex$值，然后求出$nxt$值，即下一个为该数值的下标，没有就是$0$，可以很容易$O(n)$推出来
然后考虑从$A[1]$开始删数，即考虑$A[i]$对后面的$mex$值的影响
可以发现，删去$A[i]$后，$i$到$nxt[i]-1$都会受影响，并且这个范围内$mex$大于$A[i]$的都要等于$A[i]$，这里的修改可以线段树完成，有点麻烦。那么对查询区间按左端点排序，然后依次删数，发现一个区间的$mex$值就是线段树上单点查询右端点的值。(实际上线段树上单点查询$i$表示为删了几个数$+1$到$i$之间的$mex$值)

注意此题卡输入，一定要输入优化，以后做题要测一测极限数据，看看大概时间，如果输入数据很大的话，也要考虑输入优化。

模板及讲解

数学期望

随机变量$X$的数学期望$E(X)$就是所有可能值按照概率加权的和。
$$E(X)=\sum_{i=1}^nx_ip_i$$

数学期望计算线性性质

$$E(aX+bY)=aE(X)+bE(Y)$$
$$E(XY)=E(X)+E(Y)$$

概率部分公式

($P(A|B)$表示$B$事件发生的条件下，事件$A$发生的概率。)
($P(AB)=P(A \cap B)$表示$A、B$同时发生的概率。)

1、
若$A、B$不相交，则$P(A \cup B) = P(A) + P(B)$
若$A、B$为事件，则$P(A \cup B) = P(A) + P(B) - P(AB)$(广义加法公式)

2、
若$A_1, A_2, …, A_3$互不相交，则
$P(A_1+A_2+…+A_n)=P(A_1) + P(A_2) +…P(A_n)$(加法原理)

3、
$A \in B$时$P(B-A)=P(B)-P(A)$(容斥原理)

4、
$P(AB)=0$时$P(AB) = P(A)(B)$(乘法原理)

全概率公式

$$P(A)=P(A|B_1) \times P(B_1) + P(A|B_2) \times P(B_2) + … + P(A|B_n) \times P(B_n)$$

poj 2096
设$dp(i, j)$为已经发现了$i$类bug，$j$个系统中发现了bug时要到达目标的天数期望。
明显$dp(n, s)=0$，因为已经到达了目标，所以这题要倒推，期望DP一般都要倒推来做，因为已知终态。
那么$dp(i,j)$可以由$4$个状态转移：
$dp(i+1,j+1)$, 这个bug不在已经找到的类型中，也不在已经找到bug的系统中，概率为$(1-\frac{i}{n})(1-\frac{j}{s})=\frac{(n-i)(s-j)}{ns}$(通分处理一下，这样减少除法，减小精度误差)
$dp(i+1,j)$, 这个bug不在已经找到的类型中，但在已经找到bug的系统中，概率为$(1-\frac{i}{n})\frac{j}{s}=\frac{(n-i)j}{ns}$
$dp(i,j+1)​$, 这个bug在已经找到的类型中，但不在已经找到bug的系统中，概率为$\frac{i}{n}(1-\frac{j}{s})=\frac{i(s-j)}{ns}​$
$dp(i,j)$, 这个bug不在已经找到的类型中，也不在已经找到bug的系统中，概率为$\frac{ij}{ns}$
然后根据期望运算的线性性质，得到转移方程：
$dp(i,j)=dp(i+1,j+1) \times \frac{(n-i)(s-j)}{ns} + dp(i+1,j) \times \frac{(n-i)j}{ns}$
$+ dp(i,j+1) \times \frac{i(s-j)}{ns} + dp(i,j) \times \frac{i(s-j)}{ns}+1$
其中$+1$是本次转移，就是从其他四个状态转移转移到本状态的花费。
把右边的$dp(i,j)$移到左边，有$dp(i,j)=\frac{dp(i+1,j+1) \times \frac{(n-i)(s-j)}{ns} + dp(i+1,j) \times \frac{(n-i)j}{ns} + dp(i,j+1) \times \frac{i(s-j)}{ns} +1}{1-\frac{ij}{ns}}$
然后发现有分母下都有$ns$，那么上下乘$ns$，得$dp(i,j)=\frac{dp(i+1,j+1) \times (n-i)(s-j) + dp(i+1,j) \times (n-i)j + dp(i,j+1) \times i(s-j) +ns}{ns-ij}$
经过转换，除法只有一个了，大大减小精度误差，接着倒推求解就行了，答案是$dp(0,0)$

poj 2441

用二进制来表示每个牛棚进棚情况。
设$dp(i, S)$为第$i$只奶牛$S$状态的总方案数。
则状态转移方程为
$$dp(i, S) += dp(i-1, S-j)$$
其中$j$在$S$中且$j$被$i$奶牛喜欢。
本来不想压滚动数组，但是会MLE，无奈只能压了，注意$S$就要倒过来求值了

zoj 3471
比较基础的状压，看题目数据才$n<=10$，果断状压。
用十位二进制来存储分子的存在情况，$1$为存在，$0$为不存在
设$dp(S)$为状态为$S$的最优值。
$$dp(S) = max(dp(S+j)+map(i, j))$$
注意因为是从$1$多向$1$少来转移，所以要倒推。

类似于poj1185，但是这里的影响范围是它曼哈顿距离为$2$的格子，也就是说处理状态变得复杂了很多。
设$dp(i, st(j), st(k))$为第$i$行用状态$k$，第$i-1$行用状态$j$的最优值。那么转移方程即为：
$$dp(i, st(j), st(k)) = max(dp(i, st(t), st(j)) + num(k))$$
怎么处理状态？先处理每行可行方案，1、不能有三个连续的摆放 2、不能有两个摆放之间距离为$2$
按位DP的时候，$i$上面一行对$i$行的影响只有两个方格，具体是哪个画图就知道。$i$上面第二行对$i$行的影响只有一个方格，同样具体是哪个画图就知道。

我们可以将兔子血量从小到大排序，然后对于每一个兔子，我们把能射死他的箭插入一个以价格为关键字的小根堆中，然后每次在堆中找一个最小值贡献给$ans$，对于下一个兔子，由于前面的兔子血量大于后面的兔子，所以能射死前面的兔子的箭肯定能射死这只兔子，所以不需要清空堆，直接继续插入即可，注意如果没有箭可以射死兔子说明无解.

模板及讲解

矩阵

单位矩阵：
$$
\begin{pmatrix}
1 & 0 & 0 \\\
0 & 1 & 0 \\\
0 & 0 & 1
\end{pmatrix}
$$
空矩阵：
$$
\begin{pmatrix}
0 & 0 & 0 \\\
0 & 0 & 0 \\\
0 & 0 & 0
\end{pmatrix}
$$

矩阵加法

对应位置加起来即可，矩阵加法的数初始化为空矩阵。

矩阵乘法

定义

第一个矩阵的第$i$行的每个元素乘以第二个矩阵第$j$列的每个数的积的和就是新矩阵第$i$行$j$列的数，矩阵乘法的数初始化为单位矩阵，单位矩阵乘以任意一个矩阵是不会改变值的。

写成式子，$A$大小$a \times b$，$B$大小$b \times c$，那么$C$大小为$a \times c$，则

$$C[i,j]=\sum_{k=1}^b A[i,k]B[k,j]$$

如果$A$列数不等于$B$, 则矩阵乘法无意义

存储矩阵的时候最好用结构体，因为结构体可以直接被函数返回，而且能够较为整体化

matrix mul(matrix ai, matrix bi) {//矩阵乘法 
    matrix ret; 
    ret.init2(2, 2);
    for (int i = 0; i < ai.x; i++) {
        for (int j = 0; j < bi.y; j++) {
            for (int k = 0; k < ai.y; k++) {
                ret.ma[i][j] = (ret.ma[i][j] % MO + (ai.ma[i][k] % MO) * (bi.ma[k][j] % MO)) % MO;
            }
        }
    }
    return ret;
}

结合律

矩阵乘法具有结合律。即$(AB)C=A(BC)$

证明：
$A$大小$a \times b$，$B$大小$b \times c$，$C$大小$c \times d$，则

$$((AB)C) [i,j]$$
$$=\sum_{l=1}^d(\sum_{k=1}^b A[i, k]B[k,l])C[l,j]$$
$$=\sum_{l=1}^d\sum_{k=1}^b A[i, k]B[k,l]C[l,j]$$
$$=\sum_{k=1}^b A[i, k] (\sum_{l=1}^dB[k,l]C[l,j])$$
$$=(A(BC)) [i,j]$$

结合律使得矩阵可以使用快速幂。

poj 3070

求Fibonacci数列，但是这里直接递推肯定炸。
我们根据
$$F_{n} = F_{n-1} +F_{n-2}$$
构造矩阵
$$
\begin{pmatrix}
1 & 1 \\\
1 & 0
\end{pmatrix}
\times
\begin{pmatrix}
F_{n-1} \\\
F_{n-2}
\end{pmatrix}
=
\begin{pmatrix}
F_{n} \\\
F_{n-1}
\end{pmatrix}
$$
矩阵快速幂即可。