考虑到最大前缀和的等价条件:
前缀的真后缀全>=0
前缀的补集的前缀小于0
考虑记\(S(u)\)为子表示的元素的权值和。
\(f(u)\)为满足第一个条件的方案数，\(g(u)\)为满足第二个条件的方案数。
注意到是真子集，所以我们要考虑\(s(u)\)小于\(0\)的情形。
所以记\(f(u,0),f(u,1)\)，一个为\(s(u) < 0,s(u) > 0\).
然后考虑\(f\)从后往前加，\(g\)从前往后加入，计算方案即可。
2023-12-04 10:09:22
考虑到最大前缀和的等价条件:
前缀的真后缀全>=0
前缀的补集的前缀小于0
考虑记\(S(u)\)为子表示的元素的权值和。
\(f(u)\)为满足第一个条件的方案数，\(g(u)\)为满足第二个条件的方案数。
注意到是真子集，所以我们要考虑\(s(u)\)小于\(0\)的情形。
所以记\(f(u,0),f(u,1)\)，一个为\(s(u) < 0,s(u) > 0\).
然后考虑\(f\)从后往前加，\(g\)从前往后加入，计算方案即可。