ほぼ公式解説のコピーです．
問題概要
以下では 0-based index とする．
長さ $N$ の整数列 $C$, $G$ で，$0 \leq C_i < N$，$0 \leq G_i < N$ であるものが与えられる． $0, 1, \dots, N - 1$ の順列 $P$ で，すべての $i$ について $C_{P_i} \neq G_i$ となるものの個数を mod 998244353 で求めよ．$1 \leq N \leq 2\times 10^5$．
解
$S_i := \{ P \mid C_{P_i} = G_i \}$ とすれば，求めるものは $\bigcap_{i \in \bar{N}} {S_i}^{\text{C}}$ なので，包除原理により $ \sum \left\{ (-1)^{|X|} \biggl|\bigcap_{i \in X} {S_i} \biggr| \;\middle|\; X \subseteq \bar{N} \right\} $ を求めれば良い． 包除原理についてはこのblogの記事 参照．
これは，$X \subseteq \bar{N}$ に対して，$X$ 上では選んだ色 ($C_{P_i}$) が指定された色 ($G_i$) と一致している ($X$の外ではどうなっていても良い) ような選び方 ($P$ の数) を数える，ということである． 当然，各$X$について愚直に数えていては間に合わないので，$X$を適当にグルーピングして， そのグループに属する $X$ 全体に対する $P$ の数をまとめて数えることになる．
各色 $a$ ごとに，その色が $C$ と $G$ に現れる回数を $c(a)$, $g(a)$ と書くことにする． つまり，$c(a) = |C^{-1}(a)|,\; g(a) = |G^{-1}(a)|$ (実際，$c$ と $g$ が問題の本質で，これらが一致する $C$，$G$ に対する問題の答は同一である)． 各色ごとに，その色を一致させる場所の数を定める関数 $d : \bar{N} \to \bar{N}$ を考える． 色 $a$ に対して $d(a)$ 個の場所で，選んだ色と指定された色を一致させたい，ということであるから， $d(a) \leq \min(c(a), g(a))$ となるような $d$ だけが意味を持つ． そのようなそれぞれの $d$ に対して，$|X \cap G^{-1}(a)| = d(a)$ となる $X$ を，$d$ に対応するグループとする．
- $d$ に対して，そのような $X$ の数は，$\prod_{a} \binom{g(a)}{d(a)}$ 個ある．
- $X$ 上で，選んだ色と指定された色が一致するような $P$ の数は， $(\prod_{a} \binom{c(a)}{d(a)}d(a)!) \times (N - \sum_a d(a))!$ 個である．
$|X| = \sum_a d(a)$ であるから，結局，各 $d$ に対する，次の値の和を計算すれば良いことになる:
$$(-1)^{\sum_a d(a)}(N - \sum_a d(a))! \prod_a \binom{g(a)}{d(a)}\binom{c(a)}{d(a)} d(a)!$$
次数 $\min(c(i), g(i))$ の多項式 $f_i(X)$ を，$f_i(X) := \sum_j \binom{g(i)}{j} \binom{c(i)}{j} j! X^j$ で 定義し，$f := \prod_{i = 0}^{N - 1} f_i$ とすると，求める値は，次のものになる:
$$\sum_{k = 0}^{N} (-1)^k (N - k)! ([X^k]f) $$
多項式の積は，次数の小さいものからまとめていくことで，$O(N \log^2 N)$ で計算できる．