link
壹：不合法情况
定义 \(W=1\) 的物品为一类物品，\(W=2\) 的物品为二类物品
不合法当且仅当，存在一类物品 \(x\) , \(z\) ，二类物品 \(y\)
对性价比降序排序有 \(x...(y)...z < (x)...y...(z)\) 的总收益
这种情况仅在购买 \(x\) 后总花费为 \(m-1\) 时出现
贰：计数
一
我们对不合法情况计数，然后用总方案减去它
首先对 \(a\) 降序排序
我们只需要考虑三个关键点 \(x,y,z\) 它们之间满足 $x<y<z \land 2a_y>a_x \land a_z<a_x-a_y $
此时数轴划分为若干段，有
二
定义 \(E(x,y)\) 表示已知 \(x,y\) 的情况下 \([1,y]\) 范围的非法情况个数
对于 \([1,x-1]\) 段，设二类物品有 \(p\) 个，则花费为 \(x-1+p\)
对于 \([x+1,y-1]\) 段，设一类物品有 \(q\) 个，则花费为 \(q\)
此时有 \(1+x-1+p+q=m-1\) 化简得到 \(p+q=m-1-x\)
要在 \(y-2\) 个物品中选出 \(p+q=m-1-x\) 个特殊物品，情况有 \(E(x,y)=\binom{y-2}{m-x-1}\) 种情况
三
接下来我们要拼接上z
一种显然的想法是枚举z的位置，然后求 \(E* \sum_{z=y+1}^{n} 2^{n-z-1}[a_z<a_x-a_y]\)
全部拼一块有 \(\sum_{x=1}^{n}\sum_{y=x+1}^{n}\binom{y-2}{m-x-1}\sum_{z=y+1}^{n}2^{n-z-1}[2a_y>a_x \land a_z<a_x-a_y]\)
容易发现 \(a_z\) 的下界随 \(a_y\) 的上界变小而变大 ，即 \(z\) 随着 \(y\) 右移而左移，双指针优化一维
复杂度 \(O(n^2)\)