[数学记录]AT5800 [AGC043C] Giant Graph

**题意** ： 给出三张无向图 $G_a,G_b,G_c$，点数均为 $n$ ，点的标号为 $1\sim n$。 建立一张大图 $G$，其中点为三元组 $(a,b,c)$ ，其中 $a,b,c\in 1\sim n$。 - 对于 $G_a$ 中的边 $(a,v)$ ，在 $(a,b,c)$ 与 $(v,b,c)$ 之间连边。 - 对于 $G_b$ 中的边 $(b,v)$ ，在 $(a,b,c)$ 与 $(a,v,c)$ 之间连边。 - 对于 $G_c$ 中的边 $(c,v)$ ，在 $(a,b,c)$ 与 $(a,b,v)$ 之间连边。 点 $(a,b,c)$ 的权值定义为 $10^{18(a+b+c)}$。 求图 $G$ 的最大独立集权值和，答案对 $998244353$ 取模。 $n,m\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 由于 $10^{18}$ 非常大，我们可以按照 $a+b+c$ 的顺序从大到小贪心考虑。 不难发现，对于 $a+b+c$ 相同（权值相等）的点，之间必然没有边，互不影响。 - 于是如下的贪心是正确的 ： 从大到小枚举点（权值相同顺序任意），贪心选择。 > 赛时到这里就没思路了。 考虑进一步抽象这个贪心，发掘性质。 我们为边定向，从小点连向大点，图变为了 DAG。 从大到小考虑（也是按照拓扑序从后往前考虑）若出边到达的点均没有标记，将其加入最大独立集，并打上标记。 可以发现，这和博弈论中的 $\rm N/P$ 态的定义同构。在这个 DAG 中， $\rm N$ 态即为最大独立集。 考虑如何快速判定 $(a,b,c)$ 是否为 $\rm N/P$ 态。观察到三个维度可以分别移动，且每一步只能移动一维，等同于三个游戏之和。 求出三张图中各个点的 $\rm SG$ 值 $f_a(u),f_b(u),f_c(u)$。 则答案为 ： $$\sum\limits_{f_a(x){\ \rm xor\ }f_b(y){\ \rm xor\ }f_c(z)=0}10^{18x}10^{18y}10^{18z}$$ 异或卷积即可。复杂度为 $O(n\log n)$。 - **结论** ： DAG 的 $\rm SG$ 函数的上界为 $O(\sqrt{m})$。 于是可以 $O(m)$ 进行暴力异或卷积。 ```cpp #include<algorithm> #include<cstdio> #define pb push_back #define MaxN 100500 using namespace std; const int mod=998244353,buf=716070898,lim=1024; int pw[MaxN]; struct Graph { vector<int> g[MaxN]; bool vis[MaxN],e[MaxN]; int sg[MaxN]; void dfs(int u) { if (vis[u])return ; vis[u]=1; for (int i=0;i<g[u].size();i++) dfs(g[u][i]); for (int i=0;i<g[u].size();i++) e[sg[g[u][i]]]=1; while(e[sg[u]])sg[u]++; for (int i=0;i<g[u].size();i++) e[sg[g[u][i]]]=0; } void build(int n,int *f){ int m;scanf("%d",&m); for (int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); if (u>v)swap(u,v); g[u].pb(v); } for (int i=1;i<=n;i++){ dfs(i); f[sg[i]]=(f[sg[i]]+pw[i])%mod; } } }G1,G2,G3; int n,f[1050],f1[1050],f2[1050],f3[1050]; int main() { scanf("%d",&n); pw[0]=1; for (int i=1;i<=n;i++) pw[i]=1ll*pw[i-1]*buf%mod; G1.build(n,f1);G2.build(n,f2);G3.build(n,f3); int ans=0; for (int i=0;i<lim;i++) for (int j=0;j<lim;j++) ans=(ans+1ll*f1[i]*f2[j]%mod*f3[i^j])%mod; printf("%d",ans); return 0; } ```