<span>模拟98 题解</span>
A. 线性代数 (algebra)
B. 装饰 (decoration)
暴力记录每个点的当前状态和上传状态,可以做到$O(4^n)$
注意到答案并不大,不妨设最终答案为$k$,
考虑在时间点$i$,选择点$j$对最终态的贡献,即对每一层祖先的状态取反。
所以可以直接状压$2^n$加上一个多项式的复杂度。
然后发现异或具有交换律,所以无需枚举答案,直接反向上述的过程,
当$dp_0$有值的时候,代表着第一个答案出现了。
暴力记录每个点的当前状态和上传状态,可以做到$O(4^n)$
注意到答案并不大,不妨设最终答案为$k$,
考虑在时间点$i$,选择点$j$对最终态的贡献,即对每一层祖先的状态取反。
所以可以直接状压$2^n$加上一个多项式的复杂度。
然后发现异或具有交换律,所以无需枚举答案,直接反向上述的过程,
当$dp_0$有值的时候,代表着第一个答案出现了。
相关推荐