ソースコード 拡げる

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

print(main(A, K))```

#### 提出情報

提出日時 2020-10-31 21:21:51+0900 C - Shuffle Permutation maspy Python (3.8.2) 500 1881 Byte AC 528 ms 107144 KB

#### ジャッジ結果

セット名 Sample All

 AC × 2
 AC × 25
セット名 テストケース
Sample example_00, example_01
All example_00, example_01, handmade_00, handmade_01, max_random2_00, max_random2_01, max_random2_02, max_random2_03, max_random2_04, max_random2_05, max_random2_06, max_random_00, max_random_01, max_random_02, random_00, random_01, random_02, small2_00, small2_01, small2_02, small2_03, small2_04, small_00, small_01, small_02
ケース名 結果 実行時間 メモリ
example_00 AC 528 ms 107128 KB
example_01 AC 525 ms 106244 KB
handmade_00 AC 500 ms 106288 KB
handmade_01 AC 503 ms 106548 KB
max_random2_00 AC 501 ms 106632 KB
max_random2_01 AC 504 ms 106292 KB
max_random2_02 AC 514 ms 106316 KB
max_random2_03 AC 507 ms 106416 KB
max_random2_04 AC 509 ms 107012 KB
max_random2_05 AC 503 ms 107004 KB
max_random2_06 AC 496 ms 106356 KB
max_random_00 AC 500 ms 106292 KB
max_random_01 AC 491 ms 106364 KB
max_random_02 AC 496 ms 107072 KB
random_00 AC 502 ms 106360 KB
random_01 AC 503 ms 106560 KB
random_02 AC 501 ms 107144 KB
small2_00 AC 498 ms 106352 KB
small2_01 AC 512 ms 106932 KB
small2_02 AC 503 ms 106312 KB
small2_03 AC 503 ms 106296 KB
small2_04 AC 503 ms 106276 KB
small_00 AC 500 ms 105852 KB
small_01 AC 502 ms 105900 KB
small_02 AC 502 ms 106976 KB