给定 $N,K$。要求将 $K$ 分解为 $N$ 个数，每个数均为 $1,\frac 12,\frac 14\cdots \frac 1{2^i}\cdots$询问分解方案数。
设 $\text{dp}(i,j)$ 表示需要将当前值分解为 $i$ 个数，且如果使用当前可以用的最大的数分解需要 $j$ 个的方案数。
于是假如使用一个当前可以用的最大的数，则有 $\text{dp}(i,j)\gets \text{dp}(i-1,j-1)$ 表示使用一个当前可以用的最大的数。
$\text{dp}(i,j)\gets \text{dp}(i,j<<1)$ 表示禁止使用当前可以用的最大的数。于是可以 $O(nk)$ 完成转移。
给定 $n$ 个点 $m$ 条边的无向图。图中每个点有两个权值 $a_i,b_i$。
要求选择若干点并进行删除(可以不选)，费用为所有选择的点的 $a_i$ 之和。然后收益为剩下图中每个连通块的 $b_i$ 之和的绝对值之和。
要求输出最大的收益 $-$ 费用。
对于剩下图的一个连通块的收益，要么为 $\sum b_i$，要么均为 $\sum -b_i$。
于是对于一个点，它的收益为 $-a_i,-b_i,b_i$ 三者中的一种。
同时对于原图中一条边对应的两个点 $u,v$，要满足约束不出现者两个点贡献为 $-b_u,b_v$ 或 $b_u,-b_v$ 的情况。
然后开始建图，需要最大化收益，则不妨将所有收益取相反数，然后跑最小割模型。
将一个点 $i$ 拆为 $x_i$ 和 $y_i$，然后源点 $s\to x_i$ 连一条容量为 $-b_i$ 的边，$x_i\to y_i$ 连一条容量为 $a_i$ 的边，$y_i\to t$ 连一条容量为 $b_i$ 的边。
于是这样就可以表示一个点需要从三个收益中选择一个，接下来是对约束的控制，不妨设原图中 $u,v$ 之间有一条连边。
于是 $y_v\to x_u$ 和 $y_u\to x_v$ 之间连一条权值为 $\infty$ 的边，这样就可以禁止只选择 $s\to x_u,y_v\to t$ 和 $s\to x_v,y_u\to t$ 的情况。
最后由于最小割模型不能处理负容量的边，于是考虑为原图中每个点对应的三条边加上 $|b_i|$ 的偏移量，总时间复杂度 $O(n^2(n+m))$。