[AGC043C] Giant Graph

[AGC043C] Giant Graph

因为 \(10^{18}\) 极大，所以我们将所有点按 \(x+y+z\) 排序从大往小贪心选择所有点。

根据题目连边的性质，发现不会存在 \(x+y+z\) 相同的点互相影响。

不妨建图，将边按 \(x+y+z\) 小连向大定向，这会形成一个 DAG。

我们发现一个点会被选择，当且仅当其连向的所有点都没有被选择。

这类似于博弈的必败态，仔细思考发现这确实符合必败态的定义。

我们对于这个 DAG 求出所有必败态，答案就是这些点的 \(10^{18(x+y+z)}\) 之和。

考虑和 SG 函数建立联系，我们求出每个点的 SG 函数，SG 值为 \(0\) 的点就是必败态。

首先我们发现这个游戏的 \((x,y,z)\) 三个维度是独立的，一次只能移动一个维度。

也就是说，我们求出三个维度上的 SG 函数，求异或值便可得到这个点的 SG 函数。

接下来对于每个维度上的 SG 函数，考虑直接暴力求解。

假设一个点的 SG 函数为 \(x\)，则必然会出现 SG 值为 \(0,1,\dots,x-1\) 的。

而 SG 函数为 \(x\) 会至少引出 \(x\) 条边，也就是说 \(x\) 最多是 \(O(\sqrt{m})\)。

接下来就可以暴力求解 SG 函数了，剩下的部分是一个异或卷积，直接暴力即可。

时间复杂度 \(O(m \sqrt{m})\)。

//Ad astra per aspera
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const long long mod=998244353,base=716070898;
const int V=512;
vector<int> G1[100010],G2[100010],G3[100010];
long long pow_mod[100010];
int SG1[100010],SG2[100010],SG3[100010];
long long f1[V],f2[V],f3[V];
bool flag[V];
int main(){
	int n;
	scanf("%d",&n);
	pow_mod[0]=1;
	for(int i=1;i<=n;i++){
		pow_mod[i]=pow_mod[i-1]*base%mod;
	}
	int m1;
	scanf("%d",&m1);
	while(m1--){
		int u,v;
		scanf("%d %d",&u,&v);
		G1[min(u,v)].push_back(max(u,v));
	}
	int m2;
	scanf("%d",&m2);
	while(m2--){
		int u,v;
		scanf("%d %d",&u,&v);
		G2[min(u,v)].push_back(max(u,v));
	}
	int m3;
	scanf("%d",&m3);
	while(m3--){
		int u,v;
		scanf("%d %d",&u,&v);
		G3[min(u,v)].push_back(max(u,v));
	}
	for(int u=n;u>=1;u--){
		for(int i=0;i<V;i++){
			flag[i]=false;
		}
		for(int i=0;i<G1[u].size();i++){
			int v=G1[u][i];
			flag[SG1[v]]=true;
		}
		for(int i=0;i<V;i++){
			if(!flag[i]){
				SG1[u]=i;
				break;
			}
		}
		f1[SG1[u]]+=pow_mod[u];
		f1[SG1[u]]%=mod;
	}
	for(int u=n;u>=1;u--){
		for(int i=0;i<V;i++){
			flag[i]=false;
		}
		for(int i=0;i<G2[u].size();i++){
			int v=G2[u][i];
			flag[SG2[v]]=true;
		}
		for(int i=0;i<V;i++){
			if(!flag[i]){
				SG2[u]=i;
				break;
			}
		}
		f2[SG2[u]]+=pow_mod[u];
		f2[SG2[u]]%=mod;
	}
	for(int u=n;u>=1;u--){
		for(int i=0;i<V;i++){
			flag[i]=false;
		}
		for(int i=0;i<G3[u].size();i++){
			int v=G3[u][i];
			flag[SG3[v]]=true;
		}
		for(int i=0;i<V;i++){
			if(!flag[i]){
				SG3[u]=i;
				break;
			}
		}
		f3[SG3[u]]+=pow_mod[u];
		f3[SG3[u]]%=mod;
	}
	long long ans=0;
	for(int g1=0;g1<V;g1++){
		for(int g2=0;g2<V;g2++){
			int g3=g1^g2;
			ans+=f1[g1]*f2[g2]%mod*f3[g3]%mod;
			ans%=mod;
		}
	} 
	printf("%lld",ans);
	return 0;
}