提出 #17754138

---

ソースコード 拡げる

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
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit
def fact_table(N):
    N += 1
    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD
    fact_inv = np.empty(N, np.int64)
    fact_inv[N-1] = mpow(fact[N-1], MOD-2)
    for n in range(N-1, 0, -1):
        fact_inv[n-1] = fact_inv[n] * n % MOD
    inv = np.empty(N, np.int64)
    inv[0] = 0
    inv[1:] = fact[:-1] * fact_inv[1:] % MOD
    return fact, fact_inv, inv

@njit
def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


@njit
def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

@njit((i8[:,:],i8),cache=True)
def main(A,K):
    N = len(A)
    fact, fact_inv, inv = fact_table(N+100)
    ans = 1
    for _ in range(2):
        A = A.T
        root = np.arange(N)
        size = np.ones_like(root)
        uf = (root, size)
        for i in range(N):
            for j in range(i):
                if np.all(A[i] + A[j] <= K):
                    merge(uf, i, j)
        for r in range(N):
            if find_root(uf, r) != r:
                continue
            ans = ans * fact[size[r]] % MOD
    return ans

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64).reshape(N,N)

print(main(A, K))

提出情報

ジャッジ結果