P6009 Non-Decreasing Subsequences P
由于值域很小，dp 的转移不难想到写成矩阵的形式。
考虑维护矩阵的前缀积和逆前缀积。
然而单次的矩阵乘已经达到 \(O(k^3)\) 超时了，但是我们发现其实矩阵非 \(0\) 的位置是 \(O(k)\) 个的，所以复杂度降到了 \(O(k^2)\).
关于逆矩阵，我们无需高斯消元，找规律发现非零位置也是 \(O(k)\) 个的。
如果前缀积 \(pre1_i=pre1_{i-1}\times A\)，那么注意逆前缀积是 \(pre2_i=A^{-1}\times pre2_{i-1}\).
这是因为矩阵只满足结合律。
P6142 Delegation P
考虑二分答案 \(K\)。
由于一个点往上只能伸出一条链，如果我们贪心的话一定是伸出最长的链。
考虑把儿子身上来的所有链用 multiset 维护。
如果要把若干条链两两匹配，考虑每次拉出最短的链，我们需找到最小的但是满足长度 \(\ge k\) 的链匹配。
在 multiset 上二分即可。最后剩下来那个就是向上伸的。
P6144 Help Yourself P
首先套路的使用斯特林数拆解 \(k\) 次幂，我们只需要求出所有 \(i\le k\) 的 \(C_{ans}^i\) 的和就行了。
按照左端点排序。考虑使用线段树维护 \(dp_i\) 数组表示当前最右边是 \(i\) 的答案。
设当前区间是 \([l,r]\)，对于右端点小于 \(l\) 的，那么增加了一个连通块，用 \(C_{ans}^i=C_{ans-1}^{i-1}+C_{ans-1}^i\) 更新。
对于右端点 \(\in[l,r]\) 的，可以对 \(r\) 做贡献，直接区间求和。
对于右端点大于 \(r\) 的，此时贡献不能算在 \(r\) 上，方案数都乘上 \(2\) 即可。
简单的线段树操作。
P6275 Sprinklers 2: Return of the Alfalfa P
考虑两种种物一定被一条 \((0,0)\) 到 \((n,m)\) 的分割线分成两边。
分割线的拐角一定被放置洒水器。
那么剩下的点都是放或不放，有 \(2\) 种可能。
直接设 \(dp_{i,j,0/1}\) 表示分割线到 \((i,j)\)，当前是向右/向下，\(i\) 行上面的总的贡献。
简单的转移。