sosdp 半在线

· · 算法·理论

好像染上了。病根子是啥都学不明白。然后为啥我记得我写过相关内容，怎么找不到了。
哦找到了原来是 cyq。

sosdp 见了 inf 次然后第一次用是马赛克，我没记错的话，当时还是现学的。

大概写出来就是这么个东西：

for(int i=0;i<n;i++)
for(int j=0;j<(1<<n);j++)
if(j&(1<<i))f[j]+=f[j^(1<<i)];

正确性说明是，你从高位前缀和角度去看这个东西，就是逐维做前缀和然后合并起来，于是是对的。

然后我以为后面没了。sosdp 做的东西是离线的，这个显然吧，你没法做动态计算的半在线问题，因为你对高位做合并的时候底下的信息都还没送给高位，所以爆炸了。

？junly 怎么给我扔了个半在线问题？？？？我的学习确有问题。好像是题做少了，疑似不少题都不让你离线搞都是半在线的转移。

于是来学习了：学习资料。

额仿照子集卷积（？）有一个暴力做法，你拆 popcount 然后从小到大的去搞，每次都跑一轮 sosdp 去往大了转移。

注意每轮 sosdp 只有 popcount 为当前大小的放进去初始化，然后等 popcount 在外层被遍历到的时候，该被转移到的贡献全部都拿到了，于是就搞定了。

时间复杂度 O(n^22^n)，拉完了。讨论点对的东西。

哦我好像，终于，看懂了。喜报我已经声称我自己看懂了一百万次了。

就是啥呢，外层现在是从前向后一个一个算，于是外层枚举复杂度现在是 O(2^n)。

然后呢，你维护一个 s_{i,j} 表示，前 i 位的前缀相同，j 的子集转移上来的贡献。注意这个东西只需要维护到 j 比现在枚举的外层值小的位置就可以了。

假设我们现在已经有了这个 s，如何 O(n) 算出来答案？

最最巧妙构造，我们对所有当前枚举位置是 1 的位置，假设这个对应位是 i，把这个位置变成 0 以后得到的数字是 x，我们把 s_{i,x} 拿出来就可以了。

就是，这个东西做的统计是把所有最高差异位在 i 的子集恰好拿出来，因为每个数字恰好有一个最高差异位于是做到不重不漏。

如何保证这个玩意取的是最高差异位的所有子集？我们把这个位置变成 0 了，于是这一位有差异才能进来，所以不会出现差异低了的数字。然后保证了前缀相同，于是前面不可能有差异，所以就对了。

得到答案以后，你要折回去维护 s，也就是说你要对所有前缀 i 把 s_{i,k} 给算了。k 是当前外层枚举到的数字。

那这一步的话，因为有一维是保证了多长的前缀相同，所以直接从长到短逐个解放然后合并上来就可以了。合并是跨层的。

时间复杂度 O(n2^n)，代价是空间复杂度从 O(2^n) 变成了 O(n2^n)。

大概的代码：

for(int i=0;i<(1<<n);i++){
    int sum=1;
    for(int j=0;j<n;j++)
    if(i&(1<<j))sum=(sum+s[j][i^(1<<j)])%mod;
    s[0][i]=f[i]=sum*a[i]%mod;
    for(int j=0;j<n;j++)
    if(i&(1<<j))s[j+1][i]=(s[j][i]+s[j][i^(1<<j)])%mod;
    else s[j+1][i]=s[j][i];
}

junly 老师给的作业（？）题目：P9131

把简单看成 0 困难看成 1，然后每个数字状压一下，于是变成说问有多少个子集满足能排成一个序列形如 p_1\subseteq p_2 \subseteq \dots\subseteq p_k。

那不妨先排序然后把相同数字压缩一下，变成每个数字带个权这样的，然后问题就变成和上面一样的了。

做完了？写一下。

过了。

欸，sosdp 可以半在线，那子集卷积呢？

欸我草淘到焚诀了。找机会学一下，我不会哈集幂 /ll

然后，这个东西好像不是特别平凡的，要不交个审吧（？）可能过不了，这个玩意应该算广为人知的，就只有我死于信息茧房呜呜呜。