[AGC043C] Giant Graph 题解

博主： Zi_Gao
发布时间：2024 年 05 月 27 日
641 次浏览
暂无评论
2125字数
分类： OI 题解

### 0x00 审题

首先需要知道这个 $G$ 图长什么样子。实际上根据题目的定义可以发现，$G$ 中每一个点 $(a,b,c)$ 就相当于三个人 $x,y,z$ 分别站在 $G_1,G_2,G_3$ 的 $a,b,c$ 点上。那么每经过 $G$ 上的一条边，去到相邻的点就相当于，从 $x,y,z$ 中选一个人，经过对应图上的一条边，走到相邻点。

现在定义 $G$ 上一个点 $(a,b,c)$ 的权值是 $10^{18(a+b+c)}$，求最大的独立集权值和。

### 0x01 观察性质

由于最大独立集问题是 NP 的，没有好的解决办法，所以只能从特殊性质入手解决。发现 $10^{18(a+b+c)}$ 这个点权非常奇怪，这个数非常大，这意味着在多个（最多 $n^3$ 个） $10^{18k}$ 都比不过一个 $10^{18(k+1)}$，这一点和进制很相似，那么可以转化一个独立集的点权和为 $10^{18}$ 进制的数，并且怎么加都不会进位。那么要点权最大所以考虑经典的数位贪心套路：从高位向低位贪心选点。

那么可以得到一个 $\mathcal{O}\left(n^3\right)$ 的贪心策略：

1. 把 $G$ 的点按照权值从大到小排序。
2. 从大向小考虑，若当前点与当前集合中点没有连边，则选中当前点加入集合。
3. 重复第二步，直到没有点。
4. 统计集合中点的权值和。

### 0x02 进一步转化

现在无法通过，继续观察刚才的贪心策略，由于只需要关注某一个点到比他权值更大的相邻点，这样的有指向性的偏序，令人想到可以给这个的边图定向，每一条无向边都定向成从小的点出发到大的点。注意这里有个小问题，会不会出现两个点权值一样呢，对于整个图是肯定有的，但是不会相邻，因为每一条边都只有 $(a,b,c)$ 中的一个值发生变化，而 $G_1,G_2,G_3$ 中一条边两端的点是不同的（题目限制）。这样一个无向图就变成了一个 $DAG$，为了区分是否被选中点，把能选到集合的点染成白色，不能选中的染成黑色。于是可以这样描述这个贪心过程：

1. 在 $DAG$ 上按照拓扑序依次考虑每个点。
2. 若当前的前驱有一个白点，则把这个点染成黑点；若当前点的前驱全是黑点，则把这个点染成白点。
3. 统计所有白点的权值和。

肯定终点研究第二步，动一下脑筋可以发现这个描述和博弈论的必败点、必胜点的定义是一样的：若当前点可以转化到一个必败点，则这个点是必胜点；否则若只能转化到必胜点，则这个点是必败点。在 $G$ 上把所有出度为 $0$ 的点看作结束状态必败点，则图上所有必败点就是选择到独立集中的点。

这样还是不能通过，但是把这个题转化成了一个博弈论的问题。

### 0x03 完全利用题目条件

就光这样做肯定还是不行，做不出来题一定是没有把所有条件用上。刚才分析过程中一直忽略了 $G$ 这个图的特殊形态：

> $G$ 中每一个点 $(a,b,c)$ 就相当于三个人 $x,y,z$ 分别站在 $G_1,G_2,G_3$ 的 $a,b,c$ 点上。那么每经过 $G$ 上的一条边，去到相邻的点就相当于，从 $x,y,z$ 中选一个人，经过对应图上的一条边，走到相邻点。

着意味着每次挪动点只关系到一个图，所以可以把三个都独立出来考虑。对应到博弈论模型上就是，三个有向图组合成的一个博弈游戏，根据 $SG$ 函数的知识，当这个组合游戏的必败点就是，三个图的 $SG$ 值异或在一起是 $0$。求出每个图上 $SG$ 值为 $i$ 的点的点权和 $f_{1,i},f_{2,i},f_{3,_i}$，最终的答案就是把 $f_{1,i},f_{2,i},f_{3,_i}$ 全部异或卷积起来 $g_0$ 的值。于是可以用 FWT 在 $\mathcal{O}(n\log n)$ 时间内解决。

这样有点太傻了，分析一下一个边数是 $m$ 有向图的最大 $SG$ 值不超过 $\sqrt{m}$，所以可以 $f_{1},f_{2}$ 暴力卷起来成为 $h$，然后枚举 $i\leq n$，把 $f_{3,i}\times h{i}$ 累加进答案即可。

### 0x04 代码实现

最终复杂度，求 $SG$ 值需要 $\mathcal{O}(n\log n)$，统计答案 $\mathcal{O}(m)$，总共 $\mathcal{O}(n\log n+m)$。

```cpp
#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

std::vector<int> e[100010];
long long pw[100010],f[3][510];
int sg[100010];
const long long mod=998244353;

void addEdge(int u,int v){
    e[u].push_back(v);
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

for(i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*(1000000000000000000ll%mod)%mod;

for(o=0;o<3;++o){
        m=read();
        for(i=1;i<=n;++i) e[i].clear(),sg[i]=0;
        for(i=0;i<m;++i){
            u=read();v=read();
            if(u>v) std::swap(u,v);
            addEdge(u,v);
        }
        for(u=n;u;--u){
            std::vector<int> now;
            now.push_back(-1);
            for(auto v:e[u]) now.push_back(sg[v]);
            std::sort(now.begin()+1,now.end());
            for(v=0;v+1<now.size();++v) if(now[v]+1<now[v+1]) break;
            (f[o][sg[u]=now[v]+1]+=pw[u])%=mod;
            maxsg[o]=std::max(maxsg[o],sg[u]);
        }
    }

for(i=0;i<=maxsg[0];++i)for(j=0;j<=maxsg[1];++j) (res+=f[0][i]*f[1][j]%mod*f[2][i^j])%=mod;
    print(res);

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}
```

最后修改：2024 年 05 月 27 日