题解

思路推导

一次对角线操作 $(r,r)$ 只占用编号 $r$ 对应的一行和一列；一次非对角线操作 $(r,c)$ 连同电脑的 $(c,r)$ 会同时占用编号 $r,c$ 对应的两行和两列。因此，处理完已有操作后，只需要知道还剩多少个未使用的编号。设其数量为 $m$。

剩余部分的最终局面可以看作把这 $m$ 个编号拆成若干单点和若干二元组。单点对应一次对角线操作；二元组对应一对白车、黑车，并且白车可以放在二元组的两个方向之一，所以每个二元组有两种着色方向。

设 $f_i$ 表示还有 $i$ 个编号时的局面数。固定其中一个编号：若它成为单点，剩下 $i-1$ 个编号；若它与另一个编号组成二元组，可选择另外 $i-1$ 个编号，并有两种方向，剩下 $i-2$ 个编号。因此

其中 $f_0=f_1=1$。

做法

预处理 $f_0$ 到 $f_{3\times 10^5}$。对于每组数据，令 $m=n$；读入每次已有操作时，对角线操作令 $m$ 减一，非对角线操作令 $m$ 减二。该组答案即为 $f_m$。

对于第一个子任务，可以枚举剩余编号的所有单点或配对选择，直接统计完整局面。对于第二个子任务，也可以枚举二元组数量 $x$：含 $x$ 个二元组的局面数为 $\frac{m!}{(m-2x)!x!}$，逐项直接重算乘积可得到二次算法。满分做法使用上述递推把计算降为线性预处理。

正确性证明

已有操作占用的编号以后不可能再次出现，而所有未使用编号之间的后续选择不受其原编号影响，所以剩余局面只由 $m$ 决定。

在任意最终局面中，固定的一个未使用编号恰有两类互斥去向：它单独对应一个对角线车，或与另一个编号组成一对白车、黑车。第一类与大小为 $i-1$ 的局面一一对应；第二类先选择配对编号和白车方向，再与大小为 $i-2$ 的局面一一对应，共有 $2(i-1)f_{i-2}$ 种。两类覆盖全部局面且不重不漏，故递推式成立。由边界 $f_0=f_1=1$ 归纳可知预处理值正确，输出 $f_m$ 即为答案。

复杂度分析

预处理时间复杂度为 $O(N)$，其中 $N=3\times 10^5$，空间复杂度为 $O(N)$。处理输入的总时间复杂度为 $O(N+\sum k)$。