A. 棋盘

打表发现$ans_i=ans_{i-1}*i+[i$&$1]?-1:1$

然后写高精度就完了。

所以这个式子的原型其实是：

$ans_i=ans_{i-1}*(i-1)+ans_{i-2}*(i-1)$，

其含义可以直接画图理解。

对于前一个ans的每一种方案，

可以任取一个放在最后一行，这个贡献是$ans_{i-1}$。

对于前一个ans中恰好一位不合法，放到了黑子上的一种方案，

将它不合法的一位放到最后也可以贡献一种方案，这个贡献是使其它位合法，即$ans_{i-2}$。

要证$ans_i=ans_{i-1}*i+[i$&$1]?-1:1$

只要证$ans_i=ans_{i-1}*(i-1)+ans_{i-1}+[i$&$1]?-1:1$

由$ans_i=ans_{i-1}*(i-1)+ans_{i-2}*(i-1)$

只要证$ans_{i-1}+[i$&$1]?-1:1=ans_{i-2}*(i-1)$

移项之后就可以得到$ans_{i-1}=ans_{i-2}*(i-1)+[i-1$&$1]?-1:1$

带入$i=3$，正确性是显然的，所以这个式子可以归纳证明。

另一个很好的做法是，将本题转化为错排问题，

问题为：大小为n，满足第i个元素不排在第i位的排列有多少个。

所以可以进行容斥。

设$f(i)$表示至少i个元素排在了原位，那么有：

$$f(i)=(n-i)!$$

$$ans=\sum \limits_{i=0}^{n}(-1)^i \binom{n}{i} f(i)$$

$$ans=\sum \limits_{i=0}^{n}(-1)^i \frac{n!}{i!}$$

B. 传递

直接按照给定的题意做，因为数据范围比较小，用$bitset$优化一下就可以AC。

正解是：

将P中的边插入图中，分别将Q中的边正反插入图中，

如果两次插入后都可以成功拓扑排序，那么答案为T，否则答案为N。

原因是：如果拓扑排序不能成功，那么该图中存在环。

如果存在环，那么必定存在一种情况使得P或Q不传递。

如果两次拓扑排序都成功了，因为两图的并图为竞赛图，那么P和Q都一定是合法的。

C. 异或

诡异的数位dp，并不会做。