Problem:


Score : 600 points

Problem Statement

There are 2N people numbered 1 through 2N.
The height of Person i is h_i.

How many ways are there to make N pairs of people such that the following conditions are satisfied?
Compute the answer modulo 998,244,353.

Each person is contained in exactly one pair.

For each pair, the heights of the two people in the pair are different.

Two ways are considered different if for some p and q, Person p and Person q are paired in one way and not in the other.

Constraints

1 \leq N \leq 50,000

1 \leq h_i \leq 100,000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
h_1
:
h_{2N}

Output

Print the answer.

Sample Input 1

2
1
1
2
3

Sample Output 1

2

There are two ways:

Form the pair (Person 1, Person 3) and the pair (Person 2, Person 4).

Form the pair (Person 1, Person 4) and the pair (Person 2, Person 3).

Sample Input 2

5
30
10
20
40
20
10
10
30
50
60

Sample Output 2

516



Sample input:
2
1
1
2
3


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
from heapq import *
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 mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, ), cache=True)
def fact_table(N):
    """Compute 0!, 1!, ..., (N-1)! and their inverses modulo MOD. 

    Parameters
    ----------
    N : int
        length of the output array. 

    Returns
    -------
    fact : np.ndarray
        0!, 1!, ..., (N-1)!

    fact_inv : np.ndarray
        inverse of 0!, 1!, ..., (N-1)! modulo MOD. 
    """
    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
    return fact, fact_inv

MOD = 998_244_353
MOD_root = 3
max_ntt = 18


@njit((i8, i8), cache=True)
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, i8), cache=True)
def ntt_precompute(N, primitive_root):
    roots = np.empty(1 << N, np.int64)
    iroots = np.empty(1 << N, np.int64)
    roots[0] = iroots[0] = 1
    for n in range(N):
        x = mpow(primitive_root, (MOD - 1) >> n + 2)
        y = mpow(x, MOD - 2)
        for i in range(1 << n):
            roots[(1 << n) | i] = roots[i] * x % MOD
            iroots[(1 << n) | i] = iroots[i] * y % MOD
    return roots, iroots


@njit((i8[:], i8[:], i8[:], numba.b1), cache=True)
def ntt(roots, iroots, A, inverse):
    N = len(A)
    if not inverse:
        m = N >> 1
        while m:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m] * roots[k]
                    A[i], A[i + m] = x + y, x - y
            A %= MOD
            m >>= 1
    else:
        m = 1
        while m < N:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m]
                    A[i], A[i + m] = x + y, (x - y) * iroots[k]
            A %= MOD
            m <<= 1
        for i in range(N):
            A[i] = A[i] * mpow(N, MOD - 2) % MOD
    return A


@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def ntt_convolve(roots, iroots, A, B):
    n = 0
    L = len(A) + len(B) - 1
    while (1 << n) < L:
        n += 1
    A1 = np.zeros(1 << n, np.int64)
    A1[:len(A)] = A
    B1 = np.zeros(1 << n, np.int64)
    B1[:len(B)] = B
    A, B = A1, B1
    ntt(roots, iroots, A, False)
    ntt(roots, iroots, B, False)
    for i in range(len(A)):
        A[i] = A[i] * B[i] % MOD
    ntt(roots, iroots, A, True)
    return A[:L]

@njit((i8[:], ), cache=True)
def main(H):
    max_ntt = 17
    fact, fact_inv = fact_table(100_000)
    roots, iroots = ntt_precompute(max_ntt, 3)

    def f(n, k):
        # n 人居て、k 個のペアを作る
        if k < 0 or 2 * k > n:
            return 0
        x = fact[n] * fact_inv[n - 2 * k] % MOD
        x = x * fact_inv[k] % MOD
        x = x * mpow(2, MOD - 1 - k) % MOD
        return x

    counts = np.bincount(H)
    counts = counts[counts > 0]
    N = len(counts)

    q = [(0, 0)] * 0  # 次数、インデックス
    polys = [np.zeros(0, np.int64) for _ in range(N)]
    for k in range(N):
        n = counts[k]
        P = np.empty(n // 2 + 1, np.int64)
        for i in range(n // 2 + 1):
            P[i] = f(n, i)
        polys[k] = P
        heappush(q, (len(P), k))
        
    while len(q) >= 2:
        _, i = heappop(q)
        _, j = heappop(q)
        P = polys[i]
        Q = polys[j]
        R = ntt_convolve(roots, iroots, P, Q)
        polys[i] = R
        heappush(q, (len(R), i))
    F = polys[q[0][1]]
    def any_match(n):
        # 2n 人をマッチング
        return fact[2 * n] * fact_inv[n] % MOD * mpow((MOD + 1) // 2, n) % MOD

    N = len(H) // 2
    ans = 0
    for n in range(len(F)):
        x = any_match(N - n) * F[n] % MOD
        if n & 1:
            x = -x
        ans += x
    return ans % MOD

H = np.array(read().split(), np.int64)[1:]

print(main(H))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import *
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 mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, ), cache=True)
def fact_table(N):
    """Compute 0!, 1!, ..., (N-1)! and their inverses modulo MOD. 

    Parameters
    ----------
    N : int
        length of the output array. 

    Returns
    -------
    fact : np.ndarray
        0!, 1!, ..., (N-1)!

    fact_inv : np.ndarray
        inverse of 0!, 1!, ..., (N-1)! modulo MOD. 
    """
    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
    return fact, fact_inv

MOD = 998_244_353
MOD_root = 3
max_ntt = 18


@njit((i8, i8), cache=True)
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, i8), cache=True)
def ntt_precompute(N, primitive_root):
    roots = np.empty(1 << N, np.int64)
    iroots = np.empty(1 << N, np.int64)
    roots[0] = iroots[0] = 1
    for n in range(N):
        x = mpow(primitive_root, (MOD - 1) >> n + 2)
        y = mpow(x, MOD - 2)
        for i in range(1 << n):
            roots[(1 << n) | i] = roots[i] * x % MOD
            iroots[(1 << n) | i] = iroots[i] * y % MOD
    return roots, iroots


@njit((i8[:], i8[:], i8[:], numba.b1), cache=True)
def ntt(roots, iroots, A, inverse):
    N = len(A)
    if not inverse:
        m = N >> 1
        while m:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m] * roots[k]
                    A[i], A[i + m] = x + y, x - y
            A %= MOD
            m >>= 1
    else:
        m = 1
        while m < N:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m]
                    A[i], A[i + m] = x + y, (x - y) * iroots[k]
            A %= MOD
            m <<= 1
        for i in range(N):
            A[i] = A[i] * mpow(N, MOD - 2) % MOD
    return A


@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def ntt_convolve(roots, iroots, A, B):
    n = 0
    L = len(A) + len(B) - 1
    while (1 << n) < L:
        n += 1
    A1 = np.zeros(1 << n, np.int64)
    A1[:len(A)] = A
    B1 = np.zeros(1 << n, np.int64)
    B1[:len(B)] = B
    A, B = A1, B1
    ntt(roots, iroots, A, False)
    ntt(roots, iroots, B, False)
    for i in range(len(A)):
        A[i] = A[i] * B[i] % MOD
    ntt(roots, iroots, A, True)
    return A[:L]

@njit((i8[:], ), cache=True)
def main(H):
    max_ntt = 17
    fact, fact_inv = fact_table(100_000)
    roots, iroots = ntt_precompute(max_ntt, 3)

    def f(n, k):
        # n 人居て、k 個のペアを作る
        if k < 0 or 2 * k > n:
            return 0
        x = fact[n] * fact_inv[n - 2 * k] % MOD
        x = x * fact_inv[k] % MOD
        x = x * mpow(2, MOD - 1 - k) % MOD
        return x

    counts = np.bincount(H)
    counts = counts[counts > 0]
    N = len(counts)

    q = [(0, 0)] * 0  # 次数、インデックス
    polys = [np.zeros(0, np.int64) for _ in range(N)]
    for k in range(N):
        n = counts[k]
        P = np.empty(n // 2 + 1, np.int64)
        for i in range(n // 2 + 1):
            P[i] = f(n, i)
        polys[k] = P
        heappush(q, (len(P), k))
    while len(q) >= 2:
        _, i = heappop(q)
        _, j = heappop(q)
        P = polys[i]
        Q = polys[j]
        R = ntt_convolve(roots, iroots, P, Q)
        polys[i] = R
        heappush(q, (len(R), i))
    F = polys[q[0][1]]

    def any_match(n):
        # 2n 人をマッチング
        return fact[2 * n] * fact_inv[n] % MOD * mpow((MOD + 1) // 2, n) % MOD

    N = len(H) // 2
    ans = 0
    for n in range(len(F)):
        x = any_match(N - n) * F[n] % MOD
        if n & 1:
            x = -x
        ans += x
    return ans % MOD

H = np.array(read().split(), np.int64)[1:]

print(main(H))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import *
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 mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, ), cache=True)
def fact_table(N):
    """Compute 0!, 1!, ..., (N-1)! and their inverses modulo MOD. 

    Parameters
    ----------
    N : int
        length of the output array. 

    Returns
    -------
    fact : np.ndarray
        0!, 1!, ..., (N-1)!

    fact_inv : np.ndarray
        inverse of 0!, 1!, ..., (N-1)! modulo MOD. 
    """
    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
    return fact, fact_inv

MOD = 998_244_353
MOD_root = 3
max_ntt = 18


@njit((i8, i8), cache=True)
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, i8), cache=True)
def ntt_precompute(N, primitive_root):
    roots = np.empty(1 << N, np.int64)
    iroots = np.empty(1 << N, np.int64)
    roots[0] = iroots[0] = 1
    for n in range(N):
        x = mpow(primitive_root, (MOD - 1) >> n + 2)
        y = mpow(x, MOD - 2)
        for i in range(1 << n):
            roots[(1 << n) | i] = roots[i] * x % MOD
            iroots[(1 << n) | i] = iroots[i] * y % MOD
    return roots, iroots


@njit((i8[:], i8[:], i8[:], numba.b1), cache=True)
def ntt(roots, iroots, A, inverse):
    N = len(A)
    if not inverse:
        m = N >> 1
        while m:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m] * roots[k]
                    A[i], A[i + m] = x + y, x - y
            A %= MOD
            m >>= 1
    else:
        m = 1
        while m < N:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m]
                    A[i], A[i + m] = x + y, (x - y) * iroots[k]
            A %= MOD
            m <<= 1
        for i in range(N):
            A[i] = A[i] * mpow(N, MOD - 2) % MOD
    return A


@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def ntt_convolve(roots, iroots, A, B):
    n = 0
    L = len(A) + len(B) - 1
    while (1 << n) < L:
        n += 1
    A1 = np.zeros(1 << n, np.int64)
    A1[:len(A)] = A
    B1 = np.zeros(1 << n, np.int64)
    B1[:len(B)] = B
    A, B = A1, B1
    ntt(roots, iroots, A, False)
    ntt(roots, iroots, B, False)
    for i in range(len(A)):
        A[i] = A[i] * B[i] % MOD
    ntt(roots, iroots, A, True)
    return A[:L]

@njit((i8[:], ), cache=True)
def main(H):
    max_ntt = 17
    fact, fact_inv = fact_table(100_000)
    roots, iroots = ntt_precompute(max_ntt, 3)

    def f(n, k):
        # n 人居て、k 個のペアを作る
        if k < 0 or 2 * k > n:
            return 0
        x = fact[n] * fact_inv[n - 2 * k] % MOD
        x = x * fact_inv[k] % MOD
        x = x * mpow(2, MOD - 1 - k) % MOD
        return x

    counts = np.bincount(H)
    counts = counts[counts > 0]
    N = len(counts)

    q = [(0, 0)] * 0  # 次数、インデックス
    polys = [np.zeros(0, np.int64) for _ in range(N)]
    for k in range(N):
        n = counts[k]
        P = np.empty(n // 2 + 1, np.int64)
        for i in range(n // 2 + 1):
            P[i] = f(n, i)
        polys[k] = P
        heappush(q, (len(P), k))
    while len(q) >= 2:
        _, i = heappop(q)
        _, j = heappop(q)
        P = polys[i]
        Q = polys[j]
        R = ntt_convolve(roots, iroots, P, Q)
        polys[i] = R
        heappush(q, (len(R), i))
    F = polys[q[0][1]]

    def any_match(n):
        # 2n 人をマッチング
        return fact[2 * n] * fact_inv[n] % MOD * mpow((MOD + 1) // 2, n) % MOD

    N = len(H) // 2
    ans = 0
    for n in range(len(F)):
        x = any_match(N - n) * F[n]
        if n & 1:
            x = -x
        ans += x
    return ans % MOD

H = np.array(read().split(), np.int64)[1:]

print(main(H))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import *
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 mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, ), cache=True)
def fact_table(N):
    """Compute 0!, 1!, ..., (N-1)! and their inverses modulo MOD. 

    Parameters
    ----------
    N : int
        length of the output array. 

    Returns
    -------
    fact : np.ndarray
        0!, 1!, ..., (N-1)!

    fact_inv : np.ndarray
        inverse of 0!, 1!, ..., (N-1)! modulo MOD. 
    """
    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
    return fact, fact_inv

MOD = 998_244_353
MOD_root = 3
max_ntt = 18


@njit((i8, i8), cache=True)
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, i8), cache=True)
def ntt_precompute(N, primitive_root):
    roots = np.empty(1 << N, np.int64)
    iroots = np.empty(1 << N, np.int64)
    roots[0] = iroots[0] = 1
    for n in range(N):
        x = mpow(primitive_root, (MOD - 1) >> n + 2)
        y = mpow(x, MOD - 2)
        for i in range(1 << n):
            roots[(1 << n) | i] = roots[i] * x % MOD
            iroots[(1 << n) | i] = iroots[i] * y % MOD
    return roots, iroots


@njit((i8[:], i8[:], i8[:], numba.b1), cache=True)
def ntt(roots, iroots, A, inverse):
    N = len(A)
    if not inverse:
        m = N >> 1
        while m:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m] * roots[k]
                    A[i], A[i + m] = x + y, x - y
            A %= MOD
            m >>= 1
    else:
        m = 1
        while m < N:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m]
                    A[i], A[i + m] = x + y, (x - y) * iroots[k]
            A %= MOD
            m <<= 1
        for i in range(N):
            A[i] = A[i] * mpow(N, MOD - 2) % MOD
    return A


@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def ntt_convolve(roots, iroots, A, B):
    n = 0
    L = len(A) + len(B) - 1
    while (1 << n) < L:
        n += 1
    A1 = np.zeros(1 << n, np.int64)
    A1[:len(A)] = A
    B1 = np.zeros(1 << n, np.int64)
    B1[:len(B)] = B
    A, B = A1, B1
    ntt(roots, iroots, A, False)
    ntt(roots, iroots, B, False)
    for i in range(len(A)):
        A[i] = A[i] * B[i] % MOD
    ntt(roots, iroots, A, True)
    return A[:L]

@njit((i8[:], ), cache=True)
def main(H):
    max_ntt = 17
    fact, fact_inv = fact_table(100_000)
    roots, iroots = ntt_precompute(max_ntt, 3)

    def f(n, k):
        # n 人居て、k 個のペアを作る
        if k < 0 or 2 * k > n:
            return 0
        x = fact[n] * fact_inv[n - 2 * k] % MOD
        x = x * fact_inv[k] % MOD
        x = x * mpow(2, MOD - 1 - k) % MOD
        return x

    counts = np.bincount(H)
    counts = counts[counts > 0]
    N = len(counts)

    q = [(0, 0)] * 0  # 次数、インデックス
    polys = [np.zeros(0, np.int64) for _ in range(N)]
    for k in range(N):
        n = counts[k]
        P = np.empty(n // 2 + 1, np.int64)
        for i in range(n // 2 + 1):
            P[i] = f(n, i)
        polys[k] = P
        heappush(q, (len(P), k))
    while len(q) >= 2:
        _, i = heappop(q)
        _, j = heappop(q)
        P = polys[i]
        Q = polys[j]
        R = ntt_convolve(roots, iroots, P, Q)
        polys[i] = R
        heappush(q, (len(R), i))
    F = polys[q[0][1]]

    def any_match(n):
        # 2n 人をマッチング
        return fact[2 * n] * fact_inv[n] % MOD * mpow((MOD + 1) // 2, n) % MOD

    N = len(H) // 2
    ans = 0
    for n in range(len(F)):
        x = any_match(N - n) * F[n]
        if n & 1:
            x = -x
        ans += x
    return ans

H = np.array(read().split(), np.int64)[1:]

print(main(H))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter

MOD = 998244353
def fac(limit):
    fac = [1]*limit
    for i in range(2,limit):
        fac[i] = i * fac[i-1]%MOD
    faci = [None]*limit
    faci[-1] = pow(fac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        faci[i] = faci[i+1] * (limit + i + 1) % MOD
    return fac, faci
fac, faci = fac(234139)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return fac[a]*faci[b]*faci[a-b]%MOD
def perm(a, b):
    if not a >= b >= 0:
        return 0
    return fac[a]*faci[a-b]%MOD

pr = 3
LS = 20
class NTT:
    def __init__(self):
        self.N0 = 1<<LS
        omega = pow(pr, (MOD-1)//self.N0, MOD)
        omegainv = pow(omega, MOD-2, MOD)
        self.w = [0]*(self.N0//2)
        self.winv = [0]*(self.N0//2)
        self.w[0] = 1
        self.winv[0] = 1
        for i in range(1, self.N0//2):
            self.w[i] = (self.w[i-1]*omega)%MOD
            self.winv[i] = (self.winv[i-1]*omegainv)%MOD
        used = set()
        for i in range(self.N0//2):
            if i in used:
                continue
            j = 0
            for k in range(LS-1):
                j |= (i>>k&1) << (LS-2-k)
            used.add(j)
            self.w[i], self.w[j] = self.w[j], self.w[i]
            self.winv[i], self.winv[j] = self.winv[j], self.winv[i]
        
    def _fft(self, A):
        M = len(A)
        bn = 1
        hbs = M>>1
        while hbs:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                wi = self.w[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + wi*A[j+hbs])%MOD, (A[j] - wi*A[j+hbs])%MOD
            bn <<= 1
            hbs >>= 1
 
    def _ifft(self, A):
        M = len(A)
        bn = M>>1
        hbs = 1
        while bn:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                winvi = self.winv[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + A[j+hbs])%MOD, winvi*(A[j] - A[j+hbs])%MOD
            bn >>= 1
            hbs <<= 1
    
    def convolve(self, A, B):
        LA = len(A)
        LB = len(B)
        LC = LA+LB-1
        M = 1<<(LC-1).bit_length()
        A += [0]*(M-LA)
        B += [0]*(M-LB)
        self._fft(A)
        self._fft(B)
        C = [0]*M
        for i in range(M):
            C[i] = A[i]*B[i]%MOD
        self._ifft(C)
        minv = pow(M, MOD-2, MOD)
        for i in range(LC):
            C[i] = C[i]*minv%MOD
        return C[:LC]
        
        return C
    
    def inverse(self, A):
        LA = len(A)
        dep = (LA-1).bit_length()
        M = 1<<dep
        A += [0]*(M-LA)
        
        g = [pow(A[0], MOD-2, MOD)]
        for n in range(dep):
            dl = 1<<(n+1)
            f = A[:dl]
            fg = self.convolve(f, g[:])[:dl]
            fgg = self.convolve(fg, g[:])[:dl]
            ng = [None]*dl
            for i in range(dl//2):
                ng[i] = (2*g[i]-fgg[i])%MOD
            for i in range(dl//2, dl):
                ng[i] = MOD-fgg[i]
            g = ng[:]
        return g[:LA]
    
    def integral(self, A):
        A = [1] + [A[i]*faci[i+2]%MOD for i in range(len(A))]

        
N = int(readline())
H = [int(readline()) for _ in range(2*N)]
Ch = list(Counter(H).values())
M = len(Ch)
table = [[] for _ in range(M)]


for c in Ch:
    res = [0]*(c//2 + 1)
    for i in range(c//2 + 1):
        #res[i] = perm(c, 2*i)*faci[i]%MOD
        #res[i] = comb(c, 2*i)*fac[2*i]*faci[i]%MOD
        res[i] = comb(c, 2*i)*fac[2*i]%MOD*faci[i]%MOD
    table.append(res)
 
FT = NTT()


for i in range(M-1, 0, -1):
    table[i] = FT.convolve(table[2*i], table[2*i+1])

ans = 0
for i in range(len(table[1])):
    ans = (ans + (-1 if i&1 else 1)*table[1][i]*comb(N, i)*fac[2*N-2*i]*fac[i]) % MOD
 
ans = ans*pow((MOD+1)//2, N, MOD)*faci[N]%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter

MOD = 998244353
def fac(limit):
    fac = [1]*limit
    for i in range(2,limit):
        fac[i] = i * fac[i-1]%MOD
    faci = [None]*limit
    faci[-1] = pow(fac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        faci[i] = faci[i+1] * (limit + i + 1) % MOD
    return fac, faci
fac, faci = fac(234139)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return fac[a]*faci[b]*faci[a-b]%MOD
def perm(a, b):
    if not a >= b >= 0:
        return 0
    return fac[a]*faci[a-b]%MOD

pr = 3
LS = 20
class NTT:
    def __init__(self):
        self.N0 = 1<<LS
        omega = pow(pr, (MOD-1)//self.N0, MOD)
        omegainv = pow(omega, MOD-2, MOD)
        self.w = [0]*(self.N0//2)
        self.winv = [0]*(self.N0//2)
        self.w[0] = 1
        self.winv[0] = 1
        for i in range(1, self.N0//2):
            self.w[i] = (self.w[i-1]*omega)%MOD
            self.winv[i] = (self.winv[i-1]*omegainv)%MOD
        used = set()
        for i in range(self.N0//2):
            if i in used:
                continue
            j = 0
            for k in range(LS-1):
                j |= (i>>k&1) << (LS-2-k)
            used.add(j)
            self.w[i], self.w[j] = self.w[j], self.w[i]
            self.winv[i], self.winv[j] = self.winv[j], self.winv[i]
        
    def _fft(self, A):
        M = len(A)
        bn = 1
        hbs = M>>1
        while hbs:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                wi = self.w[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + wi*A[j+hbs])%MOD, (A[j] - wi*A[j+hbs])%MOD
            bn <<= 1
            hbs >>= 1
 
    def _ifft(self, A):
        M = len(A)
        bn = M>>1
        hbs = 1
        while bn:
            for j in range(hbs):
                A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                if A[j] > MOD:
                    A[j] -= MOD
                if A[j+hbs] < 0:
                    A[j+hbs] += MOD
            for bi in range(1, bn):
                winvi = self.winv[bi]
                for j in range(bi*hbs*2, bi*hbs*2+hbs):
                    A[j], A[j+hbs] = (A[j] + A[j+hbs])%MOD, winvi*(A[j] - A[j+hbs])%MOD
            bn >>= 1
            hbs <<= 1
    
    def convolve(self, A, B):
        LA = len(A)
        LB = len(B)
        LC = LA+LB-1
        M = 1<<(LC-1).bit_length()
        A += [0]*(M-LA)
        B += [0]*(M-LB)
        self._fft(A)
        self._fft(B)
        C = [0]*M
        for i in range(M):
            C[i] = A[i]*B[i]%MOD
        self._ifft(C)
        minv = pow(M, MOD-2, MOD)
        for i in range(LC):
            C[i] = C[i]*minv%MOD
        return C[:LC]
        
        return C
    
    def inverse(self, A):
        LA = len(A)
        dep = (LA-1).bit_length()
        M = 1<<dep
        A += [0]*(M-LA)
        
        g = [pow(A[0], MOD-2, MOD)]
        for n in range(dep):
            dl = 1<<(n+1)
            f = A[:dl]
            fg = self.convolve(f, g[:])[:dl]
            fgg = self.convolve(fg, g[:])[:dl]
            ng = [None]*dl
            for i in range(dl//2):
                ng[i] = (2*g[i]-fgg[i])%MOD
            for i in range(dl//2, dl):
                ng[i] = MOD-fgg[i]
            g = ng[:]
        return g[:LA]
    
    def integral(self, A):
        A = [1] + [A[i]*faci[i+2]%MOD for i in range(len(A))]

        
N = int(readline())
H = [int(readline()) for _ in range(2*N)]
Ch = list(Counter(H).values())
M = len(Ch)
table = [[] for _ in range(M)]


for c in Ch:
    res = [0]*(c//2 + 1)
    for i in range(c//2 + 1):
        #res[i] = perm(c, 2*i)*faci[i]%MOD
        res[i] = comb(c, 2*i)*fac[2*i]*faci[i]%MOD
    table.append(res)
 
FT = NTT()


for i in range(M-1, 0, -1):
    table[i] = FT.convolve(table[2*i], table[2*i+1])

ans = 0
for i in range(len(table[1])):
    ans = (ans + (-1 if i&1 else 1)*table[1][i]*comb(N, i)*fac[2*N-2*i]*fac[i]) % MOD
 
ans = ans*pow((MOD+1)//2, N, MOD)*faci[N]%MOD
print(ans)