Problem:


Score : 900 points

Problem Statement

Given are simple undirected graphs X, Y, Z, with N vertices each and M_1, M_2, M_3 edges, respectively.
The vertices in X, Y, Z are respectively called x_1, x_2, \dots, x_N, y_1, y_2, \dots, y_N, z_1, z_2, \dots, z_N.
The edges in X, Y, Z are respectively (x_{a_i}, x_{b_i}), (y_{c_i}, y_{d_i}), (z_{e_i}, z_{f_i}).

Based on X, Y, Z, we will build another undirected graph W with N^3 vertices.
There are N^3 ways to choose a vertex from each of the graphs X, Y, Z. Each of these choices corresponds to the vertices in W one-to-one. Let (x_i, y_j, z_k) denote the vertex in W corresponding to the choice of x_i, y_j, z_k.

We will span edges in W as follows:

For each edge (x_u, x_v) in X and each w, l, span an edge between (x_u, y_w, z_l) and (x_v, y_w, z_l).

For each edge (y_u, y_v) in Y and each w, l, span an edge between (x_w, y_u, z_l) and (x_w, y_v, z_l).

For each edge (z_u, z_v) in Z and each w, l, span an edge between (x_w, y_l, z_u) and (x_w, y_l, z_v).

Then, let the weight of the vertex (x_i, y_j, z_k) in W be 1,000,000,000,000,000,000^{(i +j + k)} = 10^{18(i + j + k)}. Find the maximum possible total weight of the vertices in an independent set in W, and print that total weight modulo 998,244,353.

Constraints

2 \leq N \leq 100,000

1 \leq M_1, M_2, M_3 \leq 100,000

1 \leq a_i, b_i, c_i, d_i, e_i, f_i \leq N

X, Y, and Z are simple, that is, they have no self-loops and no multiple edges.

Input

Input is given from Standard Input in the following format:

N
M_1
a_1 b_1
a_2 b_2
\vdots
a_{M_1} b_{M_1}
M_2
c_1 d_1
c_2 d_2
\vdots
c_{M_2} d_{M_2}
M_3
e_1 f_1
e_2 f_2
\vdots
e_{M_3} f_{M_3}

Output

Print the maximum possible total weight of an independent set in W, modulo 998,244,353.

Sample Input 1

2
1
1 2
1
1 2
1
1 2

Sample Output 1

46494701

The maximum possible total weight of an independent set is that of the set (x_2, y_1, z_1), (x_1, y_2, z_1), (x_1, y_1, z_2), (x_2, y_2, z_2). The output should be (3 \times 10^{72} + 10^{108}) modulo 998,244,353, which is 46,494,701.

Sample Input 2

3
3
1 3
1 2
3 2
2
2 1
2 3
1
2 1

Sample Output 2

883188316

Sample Input 3

100000
1
1 2
1
99999 100000
1
1 100000

Sample Output 3

318525248



Sample input:
2
1
1 2
1
1 2
1
1 2


Sample output:
46494701

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((i8, i8[:, :]), cache=True)
def precompute(N, G):
    ng = np.zeros(N + 10, np.bool_)
    g = np.zeros(N + 1, np.int64)
    ind = np.searchsorted(G[:, 0], np.arange(N + 10))
    for v in range(N - 1, 0, -1):
        for i in range(ind[v], ind[v + 1]):
            w = G[i, 1]
            ng[g[w]] = 1
        for n in range(N + 10):
            if ng[n]:
                continue
            break
        g[v] = n
        for i in range(ind[v], ind[v + 1]):
            w = G[i, 1]
            ng[g[w]] = 0

    B = 10**18 % MOD
    power = 1
    A = np.zeros(1024, np.int64)
    for i in range(1, N + 1):
        power = power * B % MOD
        A[g[i]] += power
    return A % MOD

@njit((i8[:], i8[:]), cache=True)
def convolve(A, B):
    C = np.zeros(1024, np.int64)
    for i in range(1024):
        for j in range(1024):
            C[i ^ j] += A[i] * B[j] % MOD
    return C % MOD

N = int(readline())
nums = np.array(read().split(), np.int64)
graphs = []
for _ in range(3):
    M = nums[0]
    G = nums[1:1 + 2 * M].reshape(M, 2)
    G.sort(axis=1)
    graphs.append(G)
    nums = nums[1 + 2 * M:]

G1, G2, G3 = map(lambda G: precompute(N, G), graphs)

print(convolve(convolve(G1, G2), G3)[0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

M = 998244353 # < (1 << 30)

def mod_inv(a, M=M):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, M
  while abs(z1) != 1:
    d, m = divmod(z2, z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1*z1%M

R_bits = 30
R = 1 << R_bits
R_dec = R - 1
R2 = pow(R, 2, M)
M_neg_inv = mod_inv(-M, R)

def MR(x):
  b = (x * M_neg_inv) & R_dec
  t = x + b * M
  c = t >> R_bits
  d = c - M
  return d if 0 <= d else c

def Montgomery(x):
  return MR(x*R2)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(edge):
  grundy = [{} for i in range(3)]
  sum_g = [defaultdict(int, {0:M_W_sum}) for i in range(3)]
  M_W = M_W_last
  for i in range(N, 0, -1):
    for g, s, e in zip(grundy, sum_g, edge):
      if i in e:
        m = mex({g.get(j, 0) for j in e[i]})
        if m:
          g[i] = m
          s[g[i]] +=  M_W
          s[0] +=  M - M_W
    M_W = MR(M_W * M_B_inv)
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

N = int(input())
B = pow(10, 18, M)
M_B_inv = Montgomery(mod_inv(B))
M_W_last = Montgomery(pow(B, N, M))
M_W_sum = MR((M_W_last + Montgomery(-1)) * Montgomery(B * mod_inv(B-1) % M))

edge = [read_edge() for i in range(3)]
sum_g = calc_grundy(edge)
ans = 0
for gx, sx in sum_g[0].items():
  for gy, sy in sum_g[1].items():
    gz = gx^gy
    sz = sum_g[2][gz]
    if sz:
      ans += Montgomery(MR(sx)*MR(sy)*MR(sz))
print(MR(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

M = 998244353 # < (1 << 30)

def mod_inv(a, M=M):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, M
  while abs(z1) != 1:
    d, m = divmod(z2, z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1*z1%M

R_bits = 30
R = 1 << R_bits
R_dec = R - 1
R2 = pow(R, 2, M)
M_neg_inv = mod_inv(-M, R)

def MR(x):
  b = (x * M_neg_inv) & R_dec
  t = x + b * M
  c = t >> R_bits
  d = c - M
  return d if 0 <= d else c

def Montgomery(x):
  return MR(x*R2)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(edge):
  grundy = [{} for i in range(3)]
  sum_g = [defaultdict(int, {0:M_W_sum}) for i in range(3)]
  M_W = M_W_last
  for i in range(N, 0, -1):
    for g, s, e in zip(grundy, sum_g, edge):
      if i in e:
        m = mex({g.get(j, 0) for j in e[i]})
        if m:
          g[i] = m
          s[g[i]] +=  M_W
          s[0] -=  M_W
    M_W = MR(M_W * M_B_inv)
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

N = int(input())
B = pow(10, 18, M)
M_B_inv = Montgomery(mod_inv(B))
M_W_last = Montgomery(pow(B, N, M))
M_W_sum = MR((M_W_last - Montgomery(1)) * MR(Montgomery(B) * Montgomery(mod_inv(B-1))))

edge = [read_edge() for i in range(3)]
sum_g = calc_grundy(edge)
ans = 0
for gx, sx in sum_g[0].items():
  for gy, sy in sum_g[1].items():
    gz = gx^gy
    sz = sum_g[2][gz]
    if sz:
      ans += MR(MR(sx*sy)*sz)
print(MR(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

class mod_int(int):
  def __new__(cls, i=0, *args, **kwargs):
    return int.__new__(cls, i%M, *args, **kwargs)
  
  def __add__(self, x):
    return self.__class__(int.__add__(self, x))
    
  def __sub__(self, x):
    return self.__class__(int.__sub__(self, x))
    
  def __neg__(self):
    return self.__class__(int.__neg__(self, x))
  
  def __mul__(self, x):
    return self.__class__(int.__mul__(self, x))
  
  def __floordiv__(self, x):
    a, b = ext_euc(x, M)
    return self * a
  
  def __inv__(self):
    a, b = ext_euc(self, M)
    return self.__class__(a)
  
  def __pow__(self, x):
    return self.__class__(int.__pow__(self, x, M))

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(mod_int)
  sum_g[0] = (B**(N+1) - B) // (B-1)
  prev = N
  W = B**N
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      W *= B_inv**(prev-i)
      sum_g[g[i]] +=  W
      sum_g[0]  -= W
      prev, W = i, W
  
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = mod_int(0)
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret += sx*sy*sz
  return ret


M = 998244353
B = mod_int(10) ** 18
B_inv = ~B
N = int(input())

edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

M = 998244353
B = pow(10, 18, M)
N = int(input())

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
  prev_i = 1
  prev_W = B
  for i in range(1, N+1):
    if i in g:
      W = (B * pow(B, i-prev_i, M)) % M
      sum_g[g[i]] = (sum_g[g[i]] + W) % M
      sum_g[0]  = (sum_g[0] - W) % M
      prev_i, prev_W = i, W
  
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz) % M
  return ret

edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()

M = 998244353
B = pow(10, 18, M)
N = int(input())

def geometric_mod(a, r, m, n):
  x = a
  for i in range(n):
    yield x
    x = (x*r)%m

BB = list(geometric_mod(1, B, M, N+2))

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      sum_g[g[i]] = (sum_g[g[i]] + BB[i]) % M
      sum_g[0] += (sum_g[0] + BB[i]) % M
  sum_g[0] = (inv_mod(B-1, pow(B, N+1, M)-B, M) - sum_g[0]) % M
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz) % M
  return ret


edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Submission status: Time Limit Exceeded

Solution code:
def main():
    """"ここに今までのコード"""
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    n = int(readline())
    data = tuple(map(int,read().split()))
    m1 = data[0]
    ab = data[1:1+2*m1]
    m2 = data[1+2*m1]
    cd = data[2+2*m1:2+2*(m1+m2)]
    m3 = data[2+2*(m1+m2)]
    ef = data[3+2*(m1+m2):]

    mod = 998244353
    mods = [1] * (n+10)
    base = pow(10,18,mod)
    for i in range(1,n+1):
        mods[i] = (mods[i-1] * base)%mod

    def calc_node(xy):
        links = [[] for _ in range(n+1)]
        it = iter(xy)
        for x,y in zip(it,it):
            if(x < y):
                x,y = y,x
            links[y].append(x)

        group = [-1] * (n+1)
        group[-1] = 0
        num_max = 1
        for i in range(n,0,-1):
            remain = set(range(num_max+2))
            for j in links[i]:
                remain.discard(group[j])
            num = min(remain)
            group[i] = num
            num_max = max(num_max,num)

        res = [0] * (num_max+1)
        for i,num in enumerate(group[1:],1):
            res[num] += mods[i]
            res[num] %= mod

        return res

    x = calc_node(ab)
    y = calc_node(cd)
    z = calc_node(ef)

    if(len(x) < len(y)):
        x,y = y,x
    if(len(y) < len(z)):
        y,z = z,y
    if(len(x) < len(y)):
        x,y = y,x


    len_2 = 2**(len(y)-1).bit_length()
    yz = [0] * (len_2)
    for j in range(len(y)):
        for k in range(len(z)):
            yz[j^k] += y[j]*z[k]
            yz[j^k] %= mod

    ans = 0
    for i,j in zip(x,yz):
        ans += i*j
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = tuple(map(int,read().split()))
m1 = data[0]
ab = data[1:1+2*m1]
m2 = data[1+2*m1]
cd = data[2+2*m1:2+2*(m1+m2)]
m3 = data[2+2*(m1+m2)]
ef = data[3+2*(m1+m2):]

mod = 998244353
mods = [1] * (n+10)
base = pow(10,18,mod)
for i in range(1,n+1):
    mods[i] = (mods[i-1] * base)%mod

def calc_node(xy):
    links = [[] for _ in range(n+1)]
    it = iter(xy)
    for x,y in zip(it,it):
        links[x].append(y)
        links[y].append(x)

    group = [-1] * (n+1)
    group[-1] = 0
    num_max = 1
    for i in range(n,0,-1):
        remain = set(range(num_max+2))
        for j in links[i]:
            if(i < j):
                remain.discard(group[j])
        num = min(remain)
        group[i] = num
        num_max = max(num_max,num)

    res = [0] * (num_max+1)
    for i,num in enumerate(group[1:],1):
        res[num] += mods[i]
        res[num] %= mod

    return res

x = calc_node(ab)
y = calc_node(cd)
z = calc_node(ef)


if(len(x) < len(y)):
    x,y = y,x
if(len(y) < len(z)):
    y,z = z,y
if(len(x) < len(y)):
    x,y = y,x


len_2 = 2**(len(y)-1).bit_length()
yz = [0] * (len_2)
for j in range(len(y)):
    for k in range(len(z)):
        yz[j^k] += y[j]*z[k]
        yz[j^k] %= mod

ans = 0
for i,j in zip(x,yz):
    ans += i*j
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = tuple(map(int,read().split()))
m1 = data[0]
ab = data[1:1+2*m1]
m2 = data[1+2*m1]
cd = data[2+2*m1:2+2*(m1+m2)]
m3 = data[2+2*(m1+m2)]
ef = data[3+2*(m1+m2):]

mod = 998244353
mods = [1] * (n+10)
base = pow(10,18,mod)
for i in range(1,n+1):
    mods[i] = (mods[i-1] * base)%mod

def calc_node(xy):
    links = [[] for _ in range(n+1)]
    it = iter(xy)
    for x,y in zip(it,it):
        links[x].append(y)
        links[y].append(x)

    group = [-1] * (n+1)
    group[-1] = 0
    num_max = 1
    for i in range(n,0,-1):
        remain = set(range(num_max+2))
        for j in links[i]:
            if(i < j):
                remain.discard(group[j])
        num = min(remain)
        group[i] = num
        num_max = max(num_max,num)

    res = [0] * (num_max+1)
    for i,num in enumerate(group[1:],1):
        res[num] += mods[i]
        res[num] %= mod

    return res

x = calc_node(ab)
y = calc_node(cd)
z = calc_node(ef)


if(len(x) < len(y)):
    x,y = y,x
if(len(y) < len(z)):
    y,z = z,y
if(len(x) < len(y)):
    x,y = y,x


len_2 = 2**(len(y)-1).bit_length()
comb = [[] for _ in range(len_2)]
for j in range(len(y)):
    for k in range(len(z)):
        comb[j^k].append((j,k))

ans = 0
for i,x_tmp in enumerate(x):
    if(len(comb) == i):
        break

    yz = 0
    for j,k in comb[i]:
        yz += y[j]*z[k]
        yz %= mod
    ans += x_tmp * yz
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

M = 998244353
B = pow(10, 18, M)
N = int(input())

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  prev_i = N
  prev_W = pow(B, N, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      W = inv_mod(pow(B, prev_i-i, M), prev_W, M)
      sum_g[g[i]] = (sum_g[g[i]] + W) % M
      sum_g[0]  = (sum_g[0] - W) % M
      prev_i, prev_W = i, W
  
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz) % M
  return ret

edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

M = 998244353
B = pow(10, 18, M)
N = int(input())

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      x = pow(B, i, M)
      sum_g[m] += x
      sum_g[0] -= x
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = ret + sx*sy*sz
  return ret%M


edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(max(s)+2):
    if i not in s:
      return i

def calc_grandy(e):
  g = {}
  rev_g = defaultdict(set)
  rev_g[0] = set(range(1, N+1))
  for i in sorted(e.keys(), reverse=True):
    m = mex({g.get(j,0) for j in e[i]})
    if m:
      g[i] = m
      rev_g[m].add(i)
      rev_g[0].remove(i)
  return defaultdict(int, ((k,sum(map(lambda x:pow(B, x, M), v))%M) for k, v in rev_g.items()))

def get_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  grandy = list(map(calc_grandy, edge))
  ret = 0
  for gx, x in grandy[0].items():
    for gy, y in grandy[1].items():
      gz = gx^gy
      z = grandy[2][gz]
      ret = (ret + x*y*z)%M
  return ret

N = int(input())
edge = [get_edge() for i in range(3)]

print(solve(N, edge))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((i8, i8[:, :]), cache=True)
def precompute(N, G):
    ng = np.zeros(N + 10, np.bool_)
    g = np.zeros(N + 1, np.int64)
    ind = np.searchsorted(G[:, 0], np.arange(N + 10))
    for v in range(N - 1, 0, -1):
        for i in range(ind[v], ind[v + 1]):
            w = G[i, 1]
            ng[g[w]] = 1
        for n in range(N + 10):
            if ng[n]:
                continue
            break
        g[v] = n
        for i in range(ind[v], ind[v + 1]):
            w = G[i, 1]
            ng[g[w]] = 0

    B = 10**18 % MOD
    power = 1
    A = np.zeros(1024, np.int64)
    for i in range(1, N + 1):
        power = power * B % MOD
        A[g[i]] += power
    return A % MOD

@njit((i8[:], i8[:]), cache=True)
def convolve(A, B):
    C = np.zeros(1024, np.int64)
    for i in range(1024):
        for j in range(1024):
            C[i ^ j] += A[i] * B[j] % MOD
    return C % MOD

N = int(readline())
nums = np.array(read().split(), np.int64)
graphs = []
for _ in range(3):
    M = nums[0]
    G = nums[1:1 + 2 * M].reshape(M, 2)
    G.sort(axis=1)
    G = G[np.argsort(G[:, 0])]
    graphs.append(G)
    nums = nums[1 + 2 * M:]

G1, G2, G3 = map(lambda G: precompute(N, G), graphs)

print(convolve(convolve(G1, G2), G3)[0])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
N,mod=int(input()),998244353
def data():
    edge=[[] for i in range(N)]
    for i in range(int(input())):
        a,b=map(int,input().split())
        if a>b:
            a,b=b,a
        edge[a-1].append(b-1)
    mex=[0]*N
    for i in range(N-1,-1,-1):
        used=[False]*(len(edge[i])+1)
        for pv in edge[i]:
            if mex[pv]<=len(edge[i]):
                used[mex[pv]]=True
        for j in range(len(used)):
            if not used[j]:
                mex[i]=j
                break
    res=[0]*(max(mex)+1)
    for i in range(N):
        res[mex[i]]+=pow(10,18*(i+1),mod)
        res[mex[i]]%=mod
    return res
Data,ans=[data() for i in range(3)],0
for i in range(len(Data[0])):
    for j in range(len(Data[1])):
        if i^j<len(Data[2]):
            ans+=Data[0][i]*Data[1][j]*Data[2][i^j]
            ans%=mod
print(ans)

Submission status: Accepted

Solution code:
mod=998244353
inv=pow(2,mod-2,mod)

def xorconv(n,X,Y):
    if n==0:
        res=[(X[0]*Y[0])%mod]
        return res
    x=[X[i]+X[i+2**(n-1)] for i in range(2**(n-1))]
    y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))]
    z=[X[i]-X[i+2**(n-1)] for i in range(2**(n-1))]
    w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))]
    res1=xorconv(n-1,x,y)
    res2=xorconv(n-1,z,w)
    former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))]
    latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))]
    former=list(map(lambda x:x%mod,former))
    latter=list(map(lambda x:x%mod,latter))
    return former+latter

import sys

input=sys.stdin.buffer.readline

N=int(input())

def data():
    edge=[[] for i in range(N)]
    for i in range(int(input())):
        a,b=map(int,input().split())
        if a>b:
            a,b=b,a
        edge[a-1].append(b-1)
    mex=[0 for i in range(N)]
    for i in range(N-1,-1,-1):
        used=[False]*(len(edge[i])+1)
        for pv in edge[i]:
            if mex[pv]<=len(edge[i]):
                used[mex[pv]]=True
        for j in range(len(used)):
            if not used[j]:
                mex[i]=j
                break
    res=[0]*(max(mex)+1)
    for i in range(N):
        res[mex[i]]+=pow(10,18*(i+1),mod)
        res[mex[i]]%=mod

    return res

Xdata=data()
Ydata=data()
Zdata=data()

n=0
m=max(len(Xdata),len(Ydata),len(Zdata))
while 2**n<m:
    n+=1

X=[0 for i in range(2**n)]
Y=[0 for i in range(2**n)]
Z=[0 for i in range(2**n)]

for i in range(len(Xdata)):
    X[i]=Xdata[i]

for i in range(len(Ydata)):
    Y[i]=Ydata[i]

for i in range(len(Zdata)):
    Z[i]=Zdata[i]

ans=0
for i in range(2**n):
    for j in range(2**n):
        ans+=X[i]*Y[j]*Z[i^j]
        ans%=mod

print(ans)

Submission status: Accepted

Solution code:
mod=998244353
inv=pow(2,mod-2,mod)

def xorconv(n,X,Y):
    if n==0:
        res=[(X[0]*Y[0])%mod]
        return res
    x=[X[i]+X[i+2**(n-1)] for i in range(2**(n-1))]
    y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))]
    z=[X[i]-X[i+2**(n-1)] for i in range(2**(n-1))]
    w=[Y[i]-Y[i+2**(n-1)] for i in range(2**(n-1))]
    res1=xorconv(n-1,x,y)
    res2=xorconv(n-1,z,w)
    former=[(res1[i]+res2[i])*inv for i in range(2**(n-1))]
    latter=[(res1[i]-res2[i])*inv for i in range(2**(n-1))]
    former=list(map(lambda x:x%mod,former))
    latter=list(map(lambda x:x%mod,latter))
    return former+latter

import sys

input=sys.stdin.buffer.readline

N=int(input())

def data():
    edge=[[] for i in range(N)]
    for i in range(int(input())):
        a,b=map(int,input().split())
        if a>b:
            a,b=b,a
        edge[a-1].append(b-1)
    mex=[0 for i in range(N)]
    for i in range(N-1,-1,-1):
        used=[False]*(len(edge[i])+1)
        for pv in edge[i]:
            if mex[pv]<=len(edge[i]):
                used[mex[pv]]=True
        for j in range(len(used)):
            if not used[j]:
                mex[i]=j
                break
    res=[0]*(max(mex)+1)
    for i in range(N):
        res[mex[i]]+=pow(10,18*(i+1),mod)
        res[mex[i]]%=mod

    return res

Xdata=data()
Ydata=data()
Zdata=data()

n=0
m=max(len(Xdata),len(Ydata),len(Zdata))
while 2**n<m:
    n+=1

X=[0 for i in range(2**n)]
Y=[0 for i in range(2**n)]
Z=[0 for i in range(2**n)]

for i in range(len(Xdata)):
    X[i]=Xdata[i]

for i in range(len(Ydata)):
    Y[i]=Ydata[i]

for i in range(len(Zdata)):
    Z[i]=Zdata[i]

YZ=xorconv(n,Y,Z)

ans=0
for i in range(2**n):
    ans+=X[i]*YZ[i]
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

mod=998244353

N=int(input())
M1=int(input())
E1=[[] for i in range(N+1)]
for i in range(M1):
    x,y=map(int,input().split())
    E1[x].append(y)
    E1[y].append(x)

M2=int(input())
E2=[[] for i in range(N+1)]
for i in range(M2):
    x,y=map(int,input().split())
    E2[x].append(y)
    E2[y].append(x)

M3=int(input())
E3=[[] for i in range(N+1)]
for i in range(M3):
    x,y=map(int,input().split())
    E3[x].append(y)
    E3[y].append(x)

G1=[-1]*(N+1)
G1[N]=0
for i in range(N-1,-1,-1):
    GS=set()
    for to in E1[i]:
        GS.add(G1[to])
    for j in range(N+1):
        if j in GS:
            continue
        else:
            G1[i]=j
            break

G2=[-1]*(N+1)
G2[N]=0
for i in range(N-1,-1,-1):
    GS=set()
    for to in E2[i]:
        GS.add(G2[to])
    for j in range(N+1):
        if j in GS:
            continue
        else:
            G2[i]=j
            break

G3=[-1]*(N+1)
G3[N]=0
for i in range(N-1,-1,-1):
    GS=set()
    for to in E3[i]:
        GS.add(G3[to])
    for j in range(N+1):
        if j in GS:
            continue
        else:
            G3[i]=j
            break

from collections import Counter
C1=Counter()
C2=Counter()
C3=Counter()

for i in range(1,N+1):
    C1[G1[i]]=(C1[G1[i]]+pow(10,18*i,mod))%mod
    C2[G2[i]]=(C2[G2[i]]+pow(10,18*i,mod))%mod
    C3[G3[i]]=(C3[G3[i]]+pow(10,18*i,mod))%mod
        
C12=Counter()

for c1 in C1:
    for c2 in C2:
        C12[c1^c2]=(C12[c1^c2]+C1[c1]*C2[c2])%mod

ANS=0
for c3 in C3:
    ANS=(ANS+C3[c3]*C12[c3])%mod

print(ANS)

Submission status: Accepted

Solution code:
def main():
    """"ここに今までのコード"""
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    n = int(readline())
    data = tuple(map(int,read().split()))
    m1 = data[0]
    ab = data[1:1+2*m1]
    m2 = data[1+2*m1]
    cd = data[2+2*m1:2+2*(m1+m2)]
    m3 = data[2+2*(m1+m2)]
    ef = data[3+2*(m1+m2):]

    mod = 998244353
    mods = [1] * (n+10)
    base = pow(10,18,mod)
    for i in range(1,n+1):
        mods[i] = (mods[i-1] * base)%mod

    def calc_node(xy):
        links = [[] for _ in range(n+1)]
        it = iter(xy)
        for x,y in zip(it,it):
            if(x < y):
                x,y = y,x
            links[y].append(x)

        group = [-1] * (n+1)
        g_bit = [0] * (n+1)
        group[-1] = 0
        g_bit[-1] = 1
        num_max = 1
        for i in range(n,0,-1):
            tmp = 0
            for j in links[i]:
                tmp |= g_bit[j]
            cnt = 0
            while(tmp&1):
                tmp = tmp>>1
                cnt+=1
            group[i] = cnt
            g_bit[i] = 1 << cnt
            num_max = max(num_max,cnt)

        res = [0] * (num_max+1)
        for i,num in enumerate(group[1:],1):
            res[num] += mods[i]
            res[num] %= mod

        return res

    x = calc_node(ab)
    y = calc_node(cd)
    z = calc_node(ef)

    if(len(x) < len(y)):
        x,y = y,x
    if(len(y) < len(z)):
        y,z = z,y
    if(len(x) < len(y)):
        x,y = y,x


    len_2 = 2**(len(y)-1).bit_length()
    yz = [0] * (len_2)
    for j in range(len(y)):
        for k in range(len(z)):
            yz[j^k] += y[j]*z[k]
            yz[j^k] %= mod

    ans = 0
    for i,j in zip(x,yz):
        ans += i*j
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

n, *mabs = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
base = 10 ** 18 % MOD
base_costs = [base]
for i in range(n - 1):
    base_costs.append(base_costs[-1] * base % MOD)
graphs = []
i = 0
for _ in range(3):
    m = mabs[i]
    i += 1
    j = i + 2 * m
    parents = [set() for _ in range(n)]
    for a, b in zip(mabs[i:j:2], mabs[i + 1:j:2]):
        a -= 1
        b -= 1
        if a > b:
            a, b = b, a
        parents[a].add(b)
    grundy = [0] * n
    weights = defaultdict(int)
    for v in range(n - 1, -1, -1):
        pgs = {grundy[p] for p in parents[v]}
        for g in range(m + 1):
            if g not in pgs:
                grundy[v] = g
                weights[g] += base_costs[v]
                break

    for g in weights:
        weights[g] %= MOD

    graphs.append(dict(weights))
    i = j

ans = 0
graph_x, graph_y, graph_z = graphs
for gx, cx in graph_x.items():
    for gy, cy in graph_y.items():
        gz = gx ^ gy
        if gz in graph_z:
            ans = (ans + cx * cy * graph_z[gz]) % MOD
print(ans)