我们发现，如果我们将满足题意的点在数轴上标出，那么我们可以获得若干个连续段。对于一个长度为\(l\)的连续段，他对答案的贡献就是\(\frac{l(l+1)}{2}\)，我们把所有连续段的贡献加起来就得到了答案
于是我们发现这个可以拆分成子问题，具体见这篇题解。\(sol(n-mx,k-1)\)就是拆分成的子问题，因为对于\([2^c,n-1]\)这段区间的点的标记情况与\([0,n-mx-1]\)这段区间的标记情况是完全一样的（指对于\(i∈[2^c,n-1],j∈[0,n-mx-1],i=j+2^c\)，\(i\)被标记当且仅当\(j\)被标记）
中间减去的那个段相当于合并，比如下图
我们的分治算法是将绿色和红色的段当成两个段的，但实际上应该当做一个段，这个时候就要分别减去绿色的贡献和红色的贡献，再加上绿色加红色的贡献就好了
实际上我们到跟二进制有关，最多只有\(60\)位，就用的数位DP做的，但是细节比较多。只不过记住，二进制的题目也有可能拿数位DP做（当然这之前不妨想一想分治）
标签：good,标记,subarrays,Number,贡献,mx,DP From： https://www.cnblogs.com/dingxingdi/p/18345603