首先来介绍一下SOS DP
看这篇文章
解释一下，最开始的初始化for(int i=0;i<(1<<N);i++) f[i]=w[i];就是0/1背包的的初始化，可以模拟一下想一下为啥
然后是DP的过程中，注意f[st^(1<<i)]是肯定不会在这一层被更新的（因为(st^(1<<i))&(1<<i)肯定为\(0\)），所以倒序循环还是正序循环是无所谓的
然后来看看超集求和
所谓\(S\)的超集，指的是所有满足以下条件的集合\(T\)，其中\(S\)是\(T\)的子集（就是相当于\(S\)的\(1\)不变，然后\(0\)随意变化所能够得到的集合）
那么利用相同的思想，我们可以设\(dp(S,i)\)表示\(S\)的前\(i\)位其中的\(0\)随意变化能够得到的超集和，于是有
然后再来看看这道题目
看这篇文章
解释一下
相当于我现在后面较低的\(19\)位全是\(0\)了，我肯定要均匀地给每个数加一，于是有\(\frac{c}{n}\)
代码就看CF上的提交吧，代码的\(f\)和\(g\)是基于这篇题解，比如\(f[p][i]\)只的是满足第\(p\)位为\(0\)的\(i\)的超集和
标签：超集,hard,Maximum,version,Queries,DP From： https://www.cnblogs.com/dingxingdi/p/18049193