題目大意

我們稱兩個長度為 \(n\) 的數組所構成的數組對 \((a, b)\) 是合法的當且僅當其能夠滿足以下構造：

1. 構造 \(n\) 個長度為 \(3\) 且對應每一位上都不重復的使用了 \(1 \sim n\) 中的元素的數組 \(s_i\)，我們令第 \(i\) 個數組 \(s_i\) 的逆序數組為 \(t_i\)。
2. 需要滿足 \(s_i \ne t_j, s_i \ne s_j, t_i \ne t_j\)。
3. 此時將所有 \(s_i, t_i\) 按照字典序排序（以 \(1\) 為起始下標），滿足恰好 \(a_i\) 為 \(s_i\) 在其中的排名，\(b_i\) 為 \(t_i\) 在其中的排名。

現在給你兩個長度為 \(n\) 的數組 \(A, B\)，固定了 \(a_i = A_i\)，且對于 \(B_i \ne -1\) 的 \(i\)，\(b_i = B_i\)，你需要確定有多少對合法的 \((a, b)\) 滿足如上條件，對 \(998244353\) 取模。

數據范圍：\(1 \le n \le \color{red}{10^6}\)。

solution

顯然這個構造還是太吃操作了，考慮快速解決 \(B_i \ne -1\) 的情況下的答案，也就是如何判定 \((a, b)\) 是合法的。

分析一下排序后的數組，那么開頭顯然就是形如 \(1, 1, 2, 2, 3, 3, ...\)，每兩個湊成一對，由于要滿足 \(s_i \ne t_i\)，所以 \(s_i\) 的開頭和 \(t_i\) 的開頭肯定不一樣，因此 \(2i, 2i - 1\) 這兩個數不可能同時存在于 \(a\) 或 \(b\) 中，這是必要條件。

利用第二位的數值來確定合法的充要條件（因為翻轉后一樣），倘若 \(2i - 1\) 在 \(a\) 中，\(2i\) 在 \(b\) 中，那么 \(2i - 1\) 出現的位置所對應的中間數一定小于 \(2i\) 出現位置所對應的中間數，反之同理。此時我們將大小關系建圖，那么合法充要條件就是整張圖無環。

但我們顯然沒有很牛的東西統計滿足這個條件的圖的數目，將圖畫出來推理一下會發現 \(a, b\) 都確定時圖呈現為若干個對沖的環狀物，那么我們將那些還沒確定的關系給辦掉，圖的形態就是一些環狀物加上一些鏈狀物了。根據上述生成圖的方式，得出此時剩下的邊只需要滿足圖的最終形態便都是合法的，相當于說我要加一些邊，使得目前沒有環的方案數。

將每條邊固定一個方向（固定其中 \(a\) 對應的那個點，看這條邊指不指向這個點），那么無環相當于所有環狀物的方向不能一致，這里初始需要判斷一下。然后將若干條鏈組成環，使得滿足這個條件，我們設邊均為正方向的鏈數量為 \(c0\)，邊為負方向的鏈的數量為 \(c1\)，都有的鏈的數量為 \(c2\)，那么我們容斥這個化鏈為環的過程得到的答案是：

其中 \((-1)^{p + q}\) 是容斥系數，然后組合選出一些鏈，\(f_{i, j}\) 表示 \(i\) 條鏈拼成 \(j\) 個環的方案數，后面的階乘是經典結論剩下的鏈拼成若干個環的方案數。

考慮將其分為 \(i, j\) 兩部分計算，我們令 \(s_i = \sum_{j = 0}^i (-1)^j f_{i, j}\)，然后式子會變成：

此時我們算出 \(s\) 便可以 \(O(n^2)\) 求出答案，\(s\) 可以隨便 DP 一下，你可以選擇前綴和優化。此時你已經可以完美通過原題，但是本題存在嚴格線性做法。

你若是打個表便會發現 \(f_i\) 在 \(i \ge 2\) 時全部為 \(0\)，意味著通過 \(i\) 條鏈構成奇數個環和偶數個環方案數相同，具體來說可以構造雙射，拼成若干個環你可以看成時生成一個排列，取其中的置換，那么交換這個排列的第一項和第二項必然會改變置換奇偶性（具體來說是 \(+1\)，同時這也解釋了上述我們算階乘的貢獻）。