Number Of Permutations (Codeforces 1207D)
Tags: Others, combinatorics

You are given a sequence of $$$n$$$ pairs of integers: $$$(a_1, b_1), (a_2, b_2), \dots , (a_n, b_n)$$$. This sequence is called bad if it is sorted in non-descending order by first elements or if it is sorted in non-descending order by second elements. Otherwise the sequence is good. There are examples of good and bad sequences:  $$$s = [(1, 2), (3, 2), (3, 1)]$$$ is bad because the sequence of first elements is sorted: $$$[1, 3, 3]$$$;  $$$s = [(1, 2), (3, 2), (1, 2)]$$$ is bad because the sequence of second elements is sorted: $$$[2, 2, 2]$$$;  $$$s = [(1, 1), (2, 2), (3, 3)]$$$ is bad because both sequences (the sequence of first elements and the sequence of second elements) are sorted;  $$$s = [(1, 3), (3, 3), (2, 2)]$$$ is good because neither the sequence of first elements $$$([1, 3, 2])$$$ nor the sequence of second elements $$$([3, 3, 2])$$$ is sorted. Calculate the number of permutations of size $$$n$$$ such that after applying this permutation to the sequence $$$s$$$ it turns into a good sequence. A permutation $$$p$$$ of size $$$n$$$ is a sequence $$$p_1, p_2, \dots , p_n$$$ consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ ($$$1 \le p_i \le n$$$). If you apply permutation $$$p_1, p_2, \dots , p_n$$$ to the sequence $$$s_1, s_2, \dots , s_n$$$ you get the sequence $$$s_{p_1}, s_{p_2}, \dots , s_{p_n}$$$. For example, if $$$s = [(1, 2), (1, 3), (2, 3)]$$$ and $$$p = [2, 3, 1]$$$ then $$$s$$$ turns into $$$[(1, 3), (2, 3), (1, 2)]$$$.

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).The next $$$n$$$ lines contains description of sequence $$$s$$$. The $$$i$$$-th line contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — the first and second elements of $$$i$$$-th pair in the sequence.The sequence $$$s$$$ may contain equal elements.

Output: Print the number of permutations of size $$$n$$$ such that after applying this permutation to the sequence $$$s$$$ it turns into a good sequence. Print the answer modulo $$$998244353$$$ (a prime number).

Note: In first test case there are six permutations of size $$$3$$$:   if $$$p = [1, 2, 3]$$$, then $$$s = [(1, 1), (2, 2), (3, 1)]$$$ — bad sequence (sorted by first elements);  if $$$p = [1, 3, 2]$$$, then $$$s = [(1, 1), (3, 1), (2, 2)]$$$ — bad sequence (sorted by second elements);  if $$$p = [2, 1, 3]$$$, then $$$s = [(2, 2), (1, 1), (3, 1)]$$$ — good sequence;  if $$$p = [2, 3, 1]$$$, then $$$s = [(2, 2), (3, 1), (1, 1)]$$$ — good sequence;  if $$$p = [3, 1, 2]$$$, then $$$s = [(3, 1), (1, 1), (2, 2)]$$$ — bad sequence (sorted by second elements);  if $$$p = [3, 2, 1]$$$, then $$$s = [(3, 1), (2, 2), (1, 1)]$$$ — good sequence. 

Sample Inputs:
3
1 1
2 2
3 1

4
2 3
2 2
2 1
2 4

3
1 1
1 1
2 3

Sample Outputs:
3

0

4

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    n = readInt()
    (cnt1, cnt2) = ([[] for _ in range(n + 1)], [0] * (n + 1))
    for i in range(n):
        (a, b) = readInts()
        cnt1[a].append(b)
        cnt2[b] += 1
    x = y = z = 1
    ma = flag = 0
    for i in range(1, n + 1):
        x *= fac[len(cnt1[i])]
        x %= m
        y *= fac[cnt2[i]]
        y %= m
        if cnt1[i] and (not flag):
            cnt1[i].sort()
            if cnt1[i][0] < ma:
                flag = 1
            ma = cnt1[i][-1]
            if not flag:
                prev = cnt = 0
                for j in cnt1[i]:
                    if prev == j:
                        cnt += 1
                    else:
                        z *= fac[cnt]
                        z %= m
                        (cnt, prev) = (1, j)
                z *= fac[cnt]
                z %= m
    ans = x + y if flag else x + y - z
    ans %= m
    return (fac[n] - ans) % m
m = 998244353
fac = [1, 1]
for i in range(2, 3 * 10 ** 5 + 1):
    fac.append(fac[-1] * i % m)
print(solve())

Solution (Python):
import bisect
import collections
m = int(input())
res = 1
s = []
mod = 998244353
for _ in range(m):
    res = res * (_ + 1) % mod
    (x, y) = [int(i) for i in input().split()]
    s.append((x, y))
s.sort()

def func(s):
    res = 1
    d = {}
    for i in s:
        d[i] = d.get(i, 0) + 1
        res = res * d[i] % mod
    return res
res -= func([i[0] for i in s])
res -= func([i[1] for i in s])
if all((s[i][1] <= s[i + 1][1] for i in range(len(s) - 1))):
    res += func(s)
print(res % mod)

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.readline
MOD = 998244353
n = int(input())
s = sorted([tuple(map(int, input().split())) for _ in range(n)])
fact = [1]
for i in range(1, n + 1):
    fact.append(fact[-1] * i % MOD)

def ways(l):
    count = Counter(l)
    res = 1
    for x in count.values():
        res *= fact[x]
        res %= MOD
    return res
a = ways([x for (x, _) in s])
b = ways([y for (_, y) in s])
c = ways(s) if all((s[i - 1][1] <= s[i][1] for i in range(1, n))) else 0
print((fact[n] - a - b + c) % MOD)