提出 #39793562

---

ソースコード 拡げる

mod = 998244353
inv = [pow(i, mod - 2, mod) for i in range(50)]

def fast_pow(f, k, deg):
  assert f[0] == 1
  d = len(f) - 1
  g = [0] * deg
  g[0] = 1
  for a in range(1, deg):
    co = (k + 1 - a) % mod
    for i in range(1, min(a, d) + 1):
      g[a] += f[i] * g[a - i] % mod * co
      g[a] %= mod
      co = (co + k + 1) % mod
    g[a] *= inv[a]
    g[a] %= mod
  return g

def subset_pow(f, K):
  N = len(f).bit_length() - 1
  M = 1 << N
  assert len(f) == M
  pc = [0] * M
  for i in range(M):
    pc[i] = pc[i // 2] + i % 2

  F = [0] * ((N + 1) * M)
  for i in range(M):
    F[i * (N + 1) + pc[i]] = f[i]
  for lg in range(N):
    i = 1 << lg
    for j in range(0, M, 2 * i):
      for k in range(i):
        x = (j + k) * (N + 1)
        y = (i + j + k) * (N + 1)
        for l in range(N + 1):
          F[y + l] += F[x + l]
          F[y + l] %= mod

  K %= mod
  for i in range(M):
    a = F[i * (N + 1):(i + 1) * (N + 1)]
    b = fast_pow(a, K, N + 1)
    for j in range(N + 1):
      F[i * (N + 1) + j] = b[j]

  for lg in range(N):
    i = 1 << lg
    for j in range(0, M, 2 * i):
      for k in range(i):
        x = (j + k) * (N + 1)
        y = (i + j + k) * (N + 1)
        for l in range(N + 1):
          F[y + l] -= F[x + l]
          F[y + l] %= mod
  g = [0] * M
  for i in range(M):
    g[i] = F[i * (N + 1) + pc[i]]
  return g


def solve_sp(N, K, es):
  adj = [[0 for j in range(N)]for i in range(N)]
  for u, v in es:
    adj[u][v] = adj[v][u] = 1
  f = [0] * (1 << N)
  for i in range(1 << N):
    ok = 1
    for j in range(N):
      for k in range(j):
        if (i >> j) % 2 and (i >> k) % 2 and adj[j][k]:
          ok = 0
    f[i] = ok
  g = subset_pow(f, K)
  return g[-1]


import copy

def solve(N, K, _es):
  es = copy.deepcopy(_es)
  for uv in es:
    assert 0 <= uv[0] and uv[0] < N
    assert 0 <= uv[1] and uv[1] < N
    if uv[0] == uv[1]:
      return 0
  if N == 0:
    return 1

  def ch(u, v):
    for i in range(len(es)):
      if es[i][0] == u or es[i][0] == v:
        es[i][0] = u + v - es[i][0]
      if es[i][1] == u or es[i][1] == v:
        es[i][1] = u + v - es[i][1]

  deg = [0 for _ in range(N)]
  for uv in es:
    deg[uv[0]] += 1
    deg[uv[1]] += 1
  mindeg = min(deg)
  ch(deg.index(mindeg), N - 1)

  if mindeg == 0:
    return solve(N - 1, K, es) * K % mod
  if mindeg == 1:
    for j in range(len(es)):
      if max(es[j]) == N - 1:
        es.pop(j)
        break
    return solve(N - 1, K, es) * (K - 1) % mod
  if mindeg == 2:
    adj = []
    for _ in range(2):
      for j in range(len(es)):
        if max(es[j]) == N - 1:
          adj.append(es[j][0] + es[j][1] - (N - 1))
          es.pop(j)
          break
    assert len(adj) == 2
    if adj[0] == adj[1]:
      return solve(N - 1, K, es) * (K - 1) % mod
    adj.sort()
    ch(adj[1], N - 2)
    ch(adj[0], N - 3)
    ans = solve(N - 1, K, es) * (K - 2) % mod
    for j in range(len(es)):
      if es[j][0] == N - 2:
        es[j][0] = N - 3
      if es[j][1] == N - 2:
        es[j][1] = N - 3
    return (solve(N - 2, K, es) + ans) % mod

  return solve_sp(N, K, es)

def main():
  N, M, K = map(int, input().split())
  es = []
  for _ in range(M):
    u, v = map(int, input().split())
    es.append([u - 1, v - 1])
  print(solve(N, K, es))


main()

提出情報

ジャッジ結果