比赛中模拟赛的题，先来记录一下考场做法。
首先发现和普通背包问题的唯一不同就在于空间都是 \(2\) 的整数次幂的，这提示我们从这里下手。那么关于这种，我们只可能与二进制有关了，于是我们考虑选择一个在二进制上的贡献，并从高位向低位上看。我们发现，如果最高位上为 \(1\)，那么这里也只能选一个数，而如果不选的话下一位可以多选两个数。这给了我们思路。我们设 \(f(i,j)\) 表示现在考虑到了第 \(i\) 位，至多选 \(j\) 个数。那么之后发现，如果这一位上要选 \(k\) 个数的话，那么一定是选前 \(k\) 大的，那么只需要枚举这一位选几个即可。定义 \(S(i)\) 为这一位的有序集合，\(S(i,j)\) 表示前 \(j\) 个数的和。定义 \(p_x^i\) 表示 \(x\) 的第 \(i\) 二进制位的值，那么有转移：
\[f(i,j)=\max_{k=0}^{\min(|S_i|,j)}\left\{S(i,k)+f(i-1,2(j-k)+[p_m^{i-1}==1])\right\}
\]
其中 \(f(0,j)=S(0,j)\)，这样我们就获得了一个 \(O(n^2\log m)\) 的做法。但是还是不能够通过本题。并且这个东西看起来也不是非常好维护的样子。那么也一定有一些性质在里面。之后通过打表注意到对于同一个 \(i\) 满足决策单调性，于是就双指针优化到了 \(O(n\log m)\) 了。
但是比赛时要求的是这个题的加强版，还额外有 \(Q\) 次不独立的修改，每一次将一个价值加 \(1\)，并求。这个就没有办法用上面这个动规做了，需要额外想办法。