标签 FWT 下的文章

「Codeforces 662 C」Binary Table

题目链接：Codeforces 662 C

「2019 Multi-University Training Contest 2」Fantastic Magic Cube

题目链接：HDU 6596

你有一个正整数 $n$ 和一个六元组集合，我们定义六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 的权值为 $\sum_{l_{x} \le x \le r_{x}, l_{y} \le y \le r_{y}, l_{z} \le z \le r_{z}} x \oplus y \oplus z$。

初始集合中只有一个元素 $(0, n - 1, 0, n - 1, 0, n - 1)$。接下来你要重复进行以下操作，直到集合的大小为 $n ^ 3$。

• 从集合中选择一个六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 满足 $l_{x} < r_{x}$ 或 $l_{y} < r_{y}$ 或 $l_{z} < r_{z}$。

• 然后你需要从 $\{ x, y, z \}$ 中选择恰好一个元素，选择元素 $k$ 的条件是 $l_{k} < r_{k}$。

  • 如果你选择了 $x$，接下来你需要选择一个整数 $t \in [l_{x}, r_{x})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, t, l_{y}, r_{y}, l_{z}, r_{z})$ 和 $(t +1, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
  • 如果你选择了 $y$，接下来你需要选择一个整数 $t \in [l_{y}, r_{y})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, r_{x}, l_{y}, t, l_{z}, r_{z})$ 和 $(l_{x}, r_{x}, t + 1, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
  • 如果你选择了 $z$，接下来你需要选择一个整数 $t \in [l_{z}, r_{z})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, t)$ 和 $(l_{x}, r_{x}, l_{y}, r_{y}, t + 1, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。

请你求出可以获得的最大权值，答案对 $998244353$ 取模。

本题有多组数据。

数据范围：$1 \le n \le 10 ^ 6$，$1 \le \sum n \le 3 \times 10 ^ 6$。

「算法笔记」多项式模板