E - Pair of Permutations Editorial
by 
PCTprobability
\(dp[i][j] = P,Q\) を先頭 \(i\) 項まで決めて、\(P\) には現れたが \(Q\) には現れていない整数が \(j\) 個ある方法の個数という dp を考えます。
\(dp[N-M][0],dp[N-M][1],\dots,dp[N-M][M]\) が求まっているとします。\(dp[N-M][k]\) の残りの \(M\) 項の決め方は、\((1,2,\dots,M)\) の順列 \(2\) 個であって \(1,2,\dots,M-k\) は同じ位置に現れないものの個数であるため包除原理より \(\sum_{i=0}^{M-k} \binom{M-k}{i} (-1)^i M! (M-i)!\) 通りです。この値を \(A_k\) と置きます。これは畳み込みで \(\mathrm{O}(M \log M)\) で求められます。
よって、\(dp[N-M][0],dp[N-M][1],\dots,dp[N-M][M]\) を求めればよいです。ここで、\(f_j(x) = \sum_i dp[i][j] x^i\) と定義します。ただし、本来は \(dp[N-M]\) までとそれ以降で使える値が \(1\) 個ずつ増えるか増えないかの違いにより遷移が変わりますが、\(dp[N-M]\) 以降も使える値が \(1\) 個ずつ増える遷移を行うとします。
dp の遷移から、\(f_0(x) = 1 + xf_1(x),1 \le i \le M\) に対して \(f_i(x) = x((M-i+1)(M-i+2)f_{i-1}(x) + 2i(M-i+1)f_i(x) + (i+1)^2f_{i+1}(x))\) が成立します。
\(f_i(x)\) は \(x^i\) で割り切れるため、\(g_i(x) = \frac{f_i(x)}{x^i}\) に置き換えて考えます。すると、\((M-i+1)(M-i+2)g_{i-1}(x)+ (2i(M-i+1)x-1)g_i(x) + (i+1)^2x^2g_{i+1}(x) = 0\) という式が得られます。
この漸化式を後ろから解くことを考えます。
\[h_i = \begin{pmatrix} \frac{1-2i(M-i+1)x}{(M-i+1)(M-i+2)} & \frac{-(i+1)^2x^2}{(M-i+1)(M-i+2)} \\ 1 & 0 \end{pmatrix}\]
とすると、\(\begin{pmatrix} g_{i-1}(x) \\ g_i(x) \end{pmatrix} = h_i \begin{pmatrix} g_{i}(x) \\ g_{i+1}(x) \end{pmatrix}\) が成立します。つまり、\(\begin{pmatrix} g_{0}(x) \\ g_1(x) \end{pmatrix} = h_1 h_2 ... h_M \begin{pmatrix} g_{M}(x) \\ g_{M+1}(x) \end{pmatrix}\) となります。ここで、\(H = h_1 h_2 ... h_M\) と置きます。
\(g_{M+1}(x) = 0\) に注目すると、\(g_0(x) = H_{0,0} g_{M}(x),g_1(x) = H_{1,0} g_M(x)\) が得られます。また、\(g_0(x) = 1 + x^2 g_1(x)\) を利用すると、\((H_{0,0} - x^2H_{1,0})g_M(x) = 1\) が得られます。よって、\(g_M(x) = \frac{1}{H_{0,0} - x^2H_{1,0}}\) です。\(g_M(x)\) の定数項は \((M+1)!M!\) であり、今回の制約下において \(\bmod\ 998244353\) で \(0\) でないため、FPS の逆元を用いて \(g_M(x)\) を計算できます。
答えは \(\sum_{i=0}^{M} A_i dp[N-M][i] = [x^{N-M}]\sum_{i=0}^{M} A_i f_i(x) = [x^{N-M}] \sum_{i=0}^{M} A_i x^i g_i(x)\) となります。この多項式を求めるには
\[h'_i = \begin{pmatrix} \frac{1-2i(M-i+1)x}{(M-i+1)(M-i+2)} & \frac{-(i+1)^2x^2}{(M-i+1)(M-i+2)} & 0 \\ 1 & 0 & 0 \\ A_i & 0 & x \\ \end{pmatrix}\]
として \(H' = h'_1 h'_2 ... h'_M\) としたとき \([x^{N-M}] xH'_{2,0} g_M(x) + A_0 g_0(x)\) を計算すればよいです。この値は \(H'\) が求まっていれば、Bostan-Mori 法を用いて \(\mathrm{O}(M \log N \log M)\) で求めることが出来ます。
よって、行列積部分を分割統治で計算することで \(\mathrm{O}(M \log M (\log M + \log N))\) で答えを求められます。また、\(H'\) の左上の \(2 \times 2\) 部分は \(H\) と一致するため、実際に計算するのは \(H'\) だけで良いです。(オーダーは変わりませんが定数倍が良くなります。)