这个题的核心思想就是，从小到达向序列中填数，每次找当前枚举的数填了多少，然后考虑把它加到 S 中的进位问题。
我们用 f_{i,j,k,l} 表示状态：
我们每次枚举一个已经填好的状态 (i,j,k,l)，然后再枚举一个 p 表示我们填多少个 i 到序列里面。接下来讨论转移：
然后是 k，先考虑 l 的变化，此时我们的 l 就变成了 l+p。而我们接下来要填下一位了，所以我们要把第 i 位进上去，看是否保留 1。这个过程相当于二进制展开，如果最后一位是 1，也就是说 l+p 是奇数，那么我们就让这一位是 1，也就是让 k 增加 1。因此 k 会不会增加取决于 l+p 是奇数还是偶数。因此 k 转移到 k+(l+p)\%2。
最后是 l，我们需要更新进位后还没有进位的部分，因此我们令 l 转移到 (l+p)/2。
举个例子，如果 S 当前是 3-10001（“-”前面是没进位的部分），如果我们填入 2 个数，那么我们就让这个 3 变成 5，然后再进位，此时 S 就变成了 2-110001。
然后我们发现，我们需要计算填入后的数的权值以及序列的数目，因为新序列的权值和就是原序列的权值乘上新序列的权值再乘上新序列的数目。f_{i+1,j+p,k+(l+p)\%2,(l+p)/2} 加上 k 倍的 f_{i,j,k,l} 来转移。
首先权值是 v_i 的 k 次方，然后新序列的种类数需要用到插板法。问题转化为用 j 个板子分开 p 个数的方案，中间可以空。所以这部分的答案就是 j+p \choose p。所以最终的式子就是：