CF1295F Good Contest / [APIO2016] 划艇
先离散化，设 \(f_i\) 为考虑前 \(i\) 个元素的方案数，枚举第 \(i\) 个元素处在第 \(j\) 个区间，同时枚举一起在第 \(j\) 个区间的元素个数，用组合数计算方案数，\(DP\) 过程中处理组合数就是 \(O(n^3)\) 了。
第一题要算 \(n\) 个元素放到值域为 \(m\) 的区间中形成不降序列的方案数，第二题要算 \(n\) 个元素放到值域为 \(m\) 的区间中形成严格递增序列的方案数，且每个元素可以不选，但最后一个元素必须选，第一题的不降序列其实就是随便放，用隔板法即可得到 \(\binom{n+m-1}{m-1}\)，转化一下第二题的模型就能发现其方案数和第一题一样，也可以推导证明：
\[\large \sum_{i=1}^n \binom{n-1}{i-1}\binom{m}{i}=\sum_{i=0}^{n-1} \binom{n-1}{i}\binom{m}{m-i-1}=\binom{n+m-1}{m-1} \]CF1295F Good Contest [APIO2016] 划艇
CF618G Combining Slimes
输出是浮点数，发现合成到 \(50\) 以上的数字的概率已经很小了，可以忽略。
设 \(a_{i,j},b_{i,j}\) 表示用长度为 \(i\) 的格子合成数字 \(j\) 的概率，其中 \(b_{i,j}\) 表示第一个数字必须为 \(2\)，得 \(a_{i,j}=a_{i,j-1}\times a_{i-1,j-1},b_{i,j}=b_{i,j-1}\times a_{i-1,j-1}\)。不难发现当 \(i>j\) 时有 \(a_{i+1,j}=a_{i,j},b_{i+1,j}=b_{i,j}\)。
设 \({a}'_{i,j},{b}'_{i,j}\) 表示最终序列倒数第 \(i\) 个格子合成数字 \(j\) 的概率，得 \({a}'_{i,j}=a_{i,j}(1-a_{i-1,j}),{b}'_{i,j}=b_{i,j}(1-a_{i-1,j})\)。
考虑 \(DP\)，设 \(f_{i,j}\) 表示当最终序列倒数第 \(i\) 个格子为 \(j\) 时，倒数 \(i\) 个数字和的期望，得：
\[\large f_{i,j}= \begin{cases} \frac{1}{\sum\limits_{k=1}^{j-1}{a}'_{i-1,k}}\left(\sum\limits_{k=1}^{j-1}f_{i-1,k}\times {a}'_{i-1,k} \right)+j &j\neq 1 \\ \frac{1}{\sum\limits_{k=2}^{50}{b}'_{i-1,k}}\left(\sum\limits_{k=2}^{50}f_{i-1,k}\times {b}'_{i-1,k} \right)+j &j=1 \end{cases} \]预处理前 \(50\) 项后矩阵快速幂即可。
CF1307G Cow and Exercise
对原图跑费用流，设每次增广后的当前的流量总和和费用总和分别为 \(v_i,c_i\)，分类讨论即可得到每次询问的答案为 \(\min\left\{ \frac{c_i+x}{v_i} \right\}\)。
CF223E Planar Graph
选一个点作为汇点，每个点都有初始流量 \(1\)，流量都向汇点流，那么每个点流出的流量都比流入的流量大 \(1\)，于是一个环内的点的个数就是流出环的流量减去流入环的流量。以汇点为根找一棵生成树，每个点向父亲的流量就是该点的子树大小，提前对每个点的出边进行极角排序，预处理前缀和后即可快速查询。
CF708D Incorrect Flow / CF1288F Red-Blue Graph
都是有源汇上下界最小费用可行流。
CF708D Incorrect Flow CF1288F Red-Blue Graph
CF793G Oleg and chess
线段树优化建图跑费用流，扫描线的过程中动态更新线段树上的图。
[THUSCH2017] 换桌
开 \(2m\) 棵线段树优化建图跑费用流，\(m\) 棵表示从左来，\(m\) 棵表示从右来，线段树上向儿子连边时处理跨过中点的费用。
CF1100F Ivan and Burgers
离线后对询问按 \(r\) 排序，线性基中的每一位保留出现最晚的元素，在线性基上查询时，当 \(l\) 比一个元素出现时间早时，才能考虑该元素的贡献。
生成树求和 加强版
先对三进制下的每一位进行考虑，类似 CF917D Stranger Trees 一样，对每条边赋权为 \(1,x,x^2\)，矩阵树定理求行列式后用高斯消元或者插值求出多项式即可，但这样复杂度为 \(O(n^4 \log n)\)。因为循环卷积意义下的多项式的有用次数比较小，考虑直接代入多项式来求行列式，这里多项式的运算为模 \(x^3\) 意义下的循环卷积，代入 \(3\) 次单位根即可， \(3\) 次单位根有个性质：\(\omega_3^2=\omega_3-1\)，用二元组 \((a,b)\) 来表示一个数 \(a+b\omega_3\)，得其逆元为：
\[\large \frac{1}{a+b\omega_3}=\frac{a-b-b\omega_3}{(a+b\omega_3)(a-b-b\omega_3)}=\frac{a-b}{a^2+b^2-ab}-\frac{b}{a^2+b^2-ab}\omega_3 \]实际上因为 \(3\) 在本题的模数中存在二次剩余，因此二元组 \((a,b)\) 也可以直接表示复数 \(a+bi\)。总复杂度为 \(O(n^3\log n)\)。
[CERC2013] Escape
设二元组 \((a,b)\)，表示有至少 \(a\) 的血量时，可以加 \(b\) 的血量，用可并堆维护，注意当前节点的优先级最高，要与堆顶元素不断合并来更新。