[hdu6679][百度之星2019]度度熊与运算式 2

这个题我想了40分钟左右,想法比较奇妙。
显然最大答案就是把所有位置都填+号,难点在于方案数,我们考虑填异或的位置,我们必须保证每次异或之后的结果都与相加之后的结果,那么我们按异或的位置将其分成若干块,每一块中的和一定是只能包含最后答案中的某些位。比如最终答案是1011,那么我们可以拆成:1000^10^1,1000^11,1001^10,1010^1,1011。
所以我们可以直接状压取的位,进行DP。
$$f(sta)=\displaystyle\sum_{sta1\subset sta} f(sta1)[s(d(sta))\not =+]$$
其中$d(sta)$表示取这些位之后到的位置,之所以要加上这个条件是因为我们不能在固定了+号的地方放异或。
考虑优化这个DP,很容易想到cdq分治,然后我们在cdq的过程中顺便维护一个高维前缀和就可以做到$O(nlgn)$的复杂度了。

Tagged with:

发表评论