$$ f_{s|x}=f_{s}+|s|x|\sum_{y\in s}(c_{y,x}+k*c_{x,y})+|s|x|\sum_{y\ne s|x}(k*c_{y,x}-c_{x,y}) $$

令 $g_{s,x}$ 表示后面那一坨东西。

如果直接求 $g$ ,复杂度为 $\mathcal{O}(m^22^m)$ 。

$g_{s|y,x}=g_{s,x}+w_{x,y}$ ,$w_{x,y}$ 表示增量,这个是 $\mathcal{O}(m2^m)$ 。

优化空间随便搞搞即可。

有一点就是 $g_{s,x}\rightarrow h_{|s|,x}$ 。

按二进制枚举 $s$ ,$g_{s-lowbit(s),x}$ 恰好就是 $h_{|s|-1,x}$ ,这个很容易证明。