[AGC043C] Giant Graph

这题真的抽象。

注意到 \(10^{18} > n^3\)，因此只需按照 \(x+y+z\) 从大到小贪心，由于每次选点只会影响到下面若干层点的可选性，所以可以直接能选就选。时间复杂度 \(O(n^3)\)。

考虑优化，刻画一个点 \((x,y,z)\) 能选中的充要条件，即它的所有前驱都没有被选中。联想到博弈论，令可以选中的点为必败态，那么答案就是所有必败态的权值和。

关于博弈论，我们有什么武器呢？没错——\(\operatorname{SG}\) 函数。注意到三维互不影响，所以这实际上是一个简单组合游戏，可以把单个游戏的 \(\operatorname{SG}\) 函数求出来然后直接取异或和得到整个游戏的 \(\operatorname{SG}\) 函数。这样，我们把式子拆开，就变成了

这个东西是异或卷积的形式可以直接做。当然也可以注意到 \(\operatorname{SG}\) 函数的值域是根号级别然后直接枚举 \(\operatorname{SG}\) 函数值来算。

const LL P = 998244353;

const int N = 1e5 + 10;
const int B = 500;
int n;
int f[B + 10], g[B + 10], h[B + 10]; 
LL val[N];

void add(int &x, int y) {
  (x += y) >= P ? x -= P : 0;
}

vector<int> G[N];
int sg[N], m;
void solve(int *f) {
  read(m);
  for(int i = 1; i <= n; ++i)
    G[i].clear(), sg[i] = 0;
  for(int i = 1; i <= m; ++i) {
    int u, v; read(u, v);
    if(u > v) swap(u, v);
    G[u].eb(v);
  }
  for(int i = n; i >= 1; --i) {
    set<int> s;
    for(int j : G[i])
      s.insert(sg[j]);
    for(int j = 0; j <= B; ++j)
      if(s.find(j) == s.end()) {
        sg[i] = j;
        break;
      }
    add(f[sg[i]], val[i]);
  }
}

int main() {
  read(n);
  val[0] = 1, val[1] = (LL)1e18 % P;
  for(int i = 2; i <= n; ++i)
    val[i] = val[i - 1] * val[1] % P;
  solve(f), solve(g), solve(h);
  int ans = 0;
  for(int i = 0; i <= B; ++i)
    for(int j = 0; j <= B; ++j)
      add(ans, 1ll * f[i] * g[j] % P * h[i ^ j] % P);
  printf("%d\n",ans);
}