题解：AT_agc043_c [AGC043C] Giant Graph
FstAutoMaton
·
·
题解
[AGC043C] Giant Graph
一道很有教育意义的题。
题目描述
感觉题目讲的很清楚了，建议读原题题面。
题解
首先观察一下题目的一些特殊性。注意到对于点 \left(x,y,z\right)，其代价是 \left(10^{18}\right)^{x+y+z} 这件事情非常鬼畜，不妨从这一点入手。
类似很多 01-trie 上贪心的题目进行考虑，由于 10^{18} 远大于 n，所以不难发现我们肯定要尽量选择 x+y+z 大的点。于是就有了一个 \operatorname{O}(n^3) 的贪心，把每一个点都建出来，然后按照 x+y+z 从大到小选点，能选就选。
根据上面这个贪心，我们可以把无向边 \left(u,v\right) 变为一条有向边，从编号小的点连向编号大的点。这样整张图就变成了 DAG。
继续分析 最大权独立集 这个东西。令 f_{x,y,z} 表示点 \left(x,y,z\right) 有没有选，我们规定 f_{x,y,z}=0 表示选，其他情况都表示不选。设 G 表示这些 三维 的点通过这三张图连出的图，由于这是一个 DAG ，所以可以反拓扑序 dp，转移如下：
f_{x,y,z}=\operatorname{mex}_{\left(\left(x',y',z'\right),\left(x,y,z\right)\right)\in G} f_{x',y',z'}
如果出边连向的点是已经选择（即 f 值为 0）的，那么当前点的 \operatorname{mex} 值一定不会为 0，这是显然的。所以这样转移可以保证不会选择相邻的，而且我们是从权值大的点开始 dp 的，所以保证了权值最大。
观察一下，注意到 f 的 dp 与 SG 函数的计算方式很像（这也是这道题最有教育意义的地方），实际上这两个可以说一模一样。那么便考虑能否像 SG 函数一样把 若干维分开 进行 dp，最后异或在一起。
考虑 SG 函数在什么时候可以分开计算最后用异或合并，我们只要保证每一维都互不干扰。而这道题中三张图上的边都只会改变某一维的编号，所以说并不会互相干扰。于是我们可以直接拆开考虑。
设这三张图上点 x 的 SG 值分别是 F(x),G(x),H(x)，那么答案就是：
\sum_{x,y,z,F(x)\oplus G(y)\oplus H(x）=0} \left(10^{18}\right)^{x+y+z}
但这样依旧是 \operatorname{O}(n^3) 的，考虑优化.
设 F'(x) 表示在第一张图上 SG 值等于 x 的点的权值之和，G'(x)，H'(x) 同理。那么答案式子变为：
\sum_{x,y}F'(x)\times G'(y)\times H'(x \oplus y)
直接暴力是 \operatorname{O}(n^2) 的，但 SG 函数的值最大是 \operatorname{O}(\sqrt m) 级别的。感性理解一下，对于一个 SG 函数值为 x 的点，其至少需要向 \left[0,x-1\right] 中每个权值的任意一个点连边，归纳的考虑，我们想要有一个 SG 值为 x 的点至少需要 \frac{x\times \left(x+1\right)}{2} 条边，所以 SG 值是 \operatorname{O}(\sqrt{m}) 级别的。
这样我们就可以直接枚举前面答案式中的 x,y 暴力计算了，时间复杂度 \operatorname{O}(m)。
code
扩展
题目描述
在原题目的基础上，点由三维变成了 k 维，但每一维的图都是一样的（图会给定）。对于城市 \left(p_1,p_2,\cdots,p_k\right)，其代价为 10^{n^k\left(p_1+p_2+\cdots+p_k\right)}，依旧求最大权独立集。
1\le n\le 2\times 10^5,1\le k\le 10^{50000}, 1\le m\le 5\times 10^5
题解
首先这个权值显然是搞笑的，这道题怎么处理这个东西就怎么处理。至于权值计算可以用十进制倍增计算 n^k 然后费马小定理解决。
与这题一样，我们将其转化为 SG 函数的问题，由于这道题每一个维度图都一样，所以每一维的 SG 函数是一样的。
定义多项式运算：
A\cdot B=\sum_{i,x,y, x\oplus y=i} a_x\times b_y
设 SG 值为 x 的点权值和 为 f_x， F(x)=\sum_{i=0} f_i\times x^i，那么答案就是：
[x^0]F^k(x)
那么直接做的时间复杂度就是 \operatorname{O}(m\log k)，这个式子显然可以用 FWT 优化，可以优化到 \operatorname{O}(\sqrt{m}\log \sqrt{m}\log k)。
PS：这里有一个小 trick，可以直接对 k 进行十进制倍增，就不用写高精度了。
code